Created
October 27, 2011 16:34
-
-
Save mastersobg/1320066 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.*; | |
| import java.io.*; | |
| import static java.lang.Math.*; | |
| public class Main { | |
| BufferedReader in; | |
| StringTokenizer st; | |
| PrintWriter out; | |
| boolean check(int n) { | |
| if (n == 0) | |
| return false; | |
| while (n > 0) { | |
| int a = n % 10; | |
| if (a == 4 || a == 7) | |
| ; | |
| else | |
| return false; | |
| n /= 10; | |
| } | |
| return true; | |
| } | |
| boolean[] good; | |
| int[] t; | |
| void add(int idx, int add) { | |
| for (; idx < t.length; idx += idx & -idx) | |
| t[idx] += add; | |
| } | |
| int count(int idx) { | |
| if (idx == 0) | |
| return 0; | |
| int ret = 0; | |
| for (; idx > 0; idx -= idx & -idx) | |
| ret += t[idx]; | |
| return ret; | |
| } | |
| void solve() throws IOException { | |
| long begin = Calendar.getInstance().getTimeInMillis(); | |
| good = new boolean[10001]; | |
| int g = 0; | |
| for (int i = 0; i < good.length; i++) { | |
| good[i] = check(i); | |
| if (good[i]) | |
| ++g; | |
| } | |
| int n = ni(); | |
| int m = ni(); | |
| int[] v = new int[n]; | |
| t = new int[n + 10]; | |
| for (int i = 0; i < n; ++i) { | |
| v[i] = ni(); | |
| if (good[v[i]]) | |
| add(i + 1, 1); | |
| } | |
| int[] need = new int[n]; | |
| for (int it = 0; it < m; ++it) { | |
| String s = ns(); | |
| int l = ni() - 1; | |
| int r = ni() - 1; | |
| if (s.equals("add")) { | |
| int d = ni(); | |
| for (int i = l; i <= r; ++i) { | |
| if (good[v[i]]) | |
| // need[i]++; | |
| add(i + 1, -1); | |
| v[i] += d; | |
| if (good[v[i]]) | |
| // need[i]--; | |
| add(i + 1, 1); | |
| } | |
| } else { | |
| int a = count(r + 1); | |
| int b = count(l); | |
| out.println(a - b); | |
| } | |
| } | |
| System.err.println(Calendar.getInstance().getTimeInMillis() - begin); | |
| // System.err.println(g); | |
| // long begin = Calendar.getInstance().getTimeInMillis(); | |
| // int[] v = new int[100000]; | |
| // for (int i = 0; i < 10000; ++i) { | |
| // for (int j = 0; j < v.length; ++j) | |
| // v[j]++; | |
| // } | |
| // long ret = Calendar.getInstance().getTimeInMillis() - begin; | |
| // for (int a : v) | |
| // System.err.println(a); | |
| // System.err.println(ret); | |
| } | |
| void gen() throws FileNotFoundException { | |
| PrintWriter out = new PrintWriter("test.txt"); | |
| int n = 100000; | |
| int m = 10000; | |
| out.println(n + " " + m); | |
| for (int i = 0; i < n; ++i) | |
| out.println(0); | |
| for (int i = 0; i < m; ++i) { | |
| out.println("add 1 100000 1"); | |
| } | |
| out.close(); | |
| } | |
| public Main() throws IOException { | |
| // gen(); | |
| // in = new BufferedReader(new InputStreamReader(System.in)); | |
| in = new BufferedReader(new FileReader("test.txt")); | |
| out = new PrintWriter(System.out); | |
| solve(); | |
| in.close(); | |
| out.close(); | |
| } | |
| String ns() throws IOException { | |
| while (st == null || !st.hasMoreTokens()) { | |
| st = new StringTokenizer(in.readLine()); | |
| } | |
| return st.nextToken(); | |
| } | |
| int ni() throws IOException { | |
| return Integer.valueOf(ns()); | |
| } | |
| long nl() throws IOException { | |
| return Long.valueOf(ns()); | |
| } | |
| double nd() throws IOException { | |
| return Double.valueOf(ns()); | |
| } | |
| public static void main(String[] args) throws IOException { | |
| new Main(); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment