oj.uz

Submission #152789

# Submission time Handle Problem Language Result Execution time Memory
152789 2019-09-09T14:02:44 Z zeyad49 Examination (JOI19_examination) Java 11
2 / 100
 3000 ms 167936 KB 
import java.io.*;
import java.util.*;

public class examination {

	static void compress(TreeMap<Integer, Integer> map, int id) {
		for (int x : map.keySet())
			map.put(x, id++);
	}

	public static void main(String[] args) throws NumberFormatException, Exception {

		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt(), q = sc.nextInt();
		int[] s = new int[n], t = new int[n];
		Integer[] indices = new Integer[n];
		TreeMap<Integer, Integer> mapS = new TreeMap();
		for (int i = 0; i < n; i++) {
			s[i] = sc.nextInt();
			t[i] = sc.nextInt();
			indices[i] = i;
			mapS.put(s[i], 0);
		}
		Query[] queries = new Query[q];
		int[] ans = new int[q];
		for (int i = 0; i < q; i++) {
			queries[i] = new Query(sc.nextInt(), sc.nextInt(), sc.nextInt(), i);
			mapS.put(queries[i].a, 0);
		}
		compress(mapS, 1);
		Arrays.sort(queries, (x, y) -> y.c - x.c);
		Arrays.sort(indices, (x, y) -> Integer.compare(s[y] + t[y], s[x] + t[x]));
		Fenwick2D tree = new Fenwick2D(mapS.size());

		for (int i = 0; i < n; i++) {
			tree.init(mapS.get(s[i]), t[i]);
		}

		tree.init();
		int i = 0;
		for (Query query : queries) {
			while (i < n && s[indices[i]] + t[indices[i]] >= query.c) {
				int idx = indices[i++];
				tree.update(mapS.get(s[idx]), t[idx]);
			}
			ans[query.idx] = tree.query(mapS.get(query.a), query.b);

		}
		for (int x : ans)
			out.println(x);
		out.close();

	}

	static class Fenwick2D {
		TreeMap<Integer, Integer> maps[];
		FenwickTree trees[];

		Fenwick2D(int n) {

			maps = new TreeMap[n + 1];
			trees = new FenwickTree[n + 1];
			for (int i = 0; i <= n; i++)
				maps[i] = new TreeMap();
		}

		void init() {
			for (int i = 0; i < trees.length; i++) {
				int sz = maps[i].size();
				if (sz == 0)
					continue;
				trees[i] = new FenwickTree(sz);
				compress(maps[i], 1);
			}
		}

		void update(int idx, int v) {
			while (idx > 0) {
				int i = maps[idx].get(v);
				trees[idx].update(i, 1);
				idx -= (idx & -idx);
			}
		}

		void init(int idx, int v) {
			while (idx > 0) {
				maps[idx].put(v, 0);
				idx -= (idx & -idx);
			}
		}

		int query(int idx, int b) {
			int ans = 0;
			while (idx < trees.length) {
				Integer hi = maps[idx].ceilingKey(b);
				if (hi != null)
					ans += trees[idx].query(maps[idx].get(hi));
				idx += idx & -idx;
			}
			return ans;
		}

	}

	static class FenwickTree {
		int[] bit;

		FenwickTree(int n) {
			bit = new int[n + 1];
		}

		int query(int idx) {
			int ans = 0;
			while (idx < bit.length) {
				ans += bit[idx];
				idx += (idx & -idx);
			}
			return ans;
		}

		void update(int idx, int v) {
			while (idx > 0) {
				bit[idx] += v;
				idx -= idx & -idx;
			}
		}

	}

	static class Query {
		int a, b, c, idx;

		Query(int a, int b, int c, int idx) {
			this.a = a;
			this.b = b;
			this.c = c;
			this.idx = idx;
		}
	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		Scanner(String fileName) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(fileName));
		}

		String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}

	}
}

Compilation message

Note: examination.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 16384 KB Output is correct
2 Correct 225 ms 15756 KB Output is correct
3 Correct 226 ms 15588 KB Output is correct
4 Correct 219 ms 14992 KB Output is correct
5 Correct 230 ms 15488 KB Output is correct
6 Correct 234 ms 15160 KB Output is correct
7 Correct 566 ms 24436 KB Output is correct
8 Correct 562 ms 24168 KB Output is correct
9 Correct 531 ms 23304 KB Output is correct
10 Correct 532 ms 23628 KB Output is correct
11 Correct 516 ms 24176 KB Output is correct
12 Correct 465 ms 21416 KB Output is correct
13 Correct 555 ms 24684 KB Output is correct
14 Correct 527 ms 23384 KB Output is correct
15 Correct 572 ms 24540 KB Output is correct
16 Correct 463 ms 21256 KB Output is correct
17 Correct 559 ms 21936 KB Output is correct
18 Correct 401 ms 21660 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3382 ms 167936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3382 ms 167936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 16384 KB Output is correct
2 Correct 225 ms 15756 KB Output is correct
3 Correct 226 ms 15588 KB Output is correct
4 Correct 219 ms 14992 KB Output is correct
5 Correct 230 ms 15488 KB Output is correct
6 Correct 234 ms 15160 KB Output is correct
7 Correct 566 ms 24436 KB Output is correct
8 Correct 562 ms 24168 KB Output is correct
9 Correct 531 ms 23304 KB Output is correct
10 Correct 532 ms 23628 KB Output is correct
11 Correct 516 ms 24176 KB Output is correct
12 Correct 465 ms 21416 KB Output is correct
13 Correct 555 ms 24684 KB Output is correct
14 Correct 527 ms 23384 KB Output is correct
15 Correct 572 ms 24540 KB Output is correct
16 Correct 463 ms 21256 KB Output is correct
17 Correct 559 ms 21936 KB Output is correct
18 Correct 401 ms 21660 KB Output is correct
19 Execution timed out 3382 ms 167936 KB Time limit exceeded
20 Halted 0 ms 0 KB -