oj.uz

Submission #152721

# Submission time Handle Problem Language Result Execution time Memory
152721 2019-09-09T09:38:55 Z zeyad49 Examination (JOI19_examination) Java 11
2 / 100
 3000 ms 180492 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, 0);
		Arrays.sort(queries, (x, y) -> y.c - x.c);
		Arrays.sort(indices, (x, y) -> Integer.compare(s[y] + t[y], s[x] + t[x]));
		SegmentTree tree = new SegmentTree(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), mapS.size() - 1, query.b);

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

	static class SegmentTree {
		TreeMap<Integer, Integer> maps[];
		FenwickTree trees[];
		int n;

		SegmentTree(int n) {
			this.n = n;
			maps = new TreeMap[4 * n];
			trees = new FenwickTree[4 * n];
			for (int i = 0; i < 4 * n; i++)
				maps[i] = new TreeMap();
		}

		void update(int idx, int v) {
			update(1, 0, n - 1, idx, v);
		}

		void init(int idx, int v) {
			init(1, 0, n - 1, idx, v);
		}

		void init(int node, int tl, int tr, int idx, int v) {
			maps[node].put(v, 0);
			if (tl != tr) {
				int mid = tl + tr >> 1, left = node << 1, right = left | 1;
				if (idx <= mid)
					init(left, tl, mid, idx, v);
				else
					init(right, mid + 1, tr, idx, v);
			}
		}

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

			}
		}

		void update(int node, int tl, int tr, int idx, int v) {
			int i = maps[node].get(v);
			trees[node].update(i, 1);
			if (tl != tr) {
				int mid = tl + tr >> 1, left = node << 1, right = left | 1;
				if (idx <= mid)
					update(left, tl, mid, idx, v);
				else
					update(right, mid + 1, tr, idx, v);
			}
		}

		int query(int l, int r, int b) {
			return query(1, 0, n - 1, l, r, b);
		}

		int query(int node, int tl, int tr, int l, int r, int b) {
			if (r < tl || tr < l)
				return 0;
			if (tl >= l && tr <= r) {
				Integer hi = maps[node].ceilingKey(b);

				return hi == null ? 0 : trees[node].query(maps[node].get(hi));
			}
			int mid = tl + tr >> 1, left = node << 1, right = left | 1;
			return query(left, tl, mid, l, r, b) + query(right, mid + 1, tr, l, r, b);
		}

	}

	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));
		}

		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 234 ms 16392 KB Output is correct
2 Correct 225 ms 15608 KB Output is correct
3 Correct 221 ms 15448 KB Output is correct
4 Correct 224 ms 15760 KB Output is correct
5 Correct 227 ms 15652 KB Output is correct
6 Correct 219 ms 15112 KB Output is correct
7 Correct 651 ms 30332 KB Output is correct
8 Correct 643 ms 29928 KB Output is correct
9 Correct 657 ms 30880 KB Output is correct
10 Correct 570 ms 24692 KB Output is correct
11 Correct 529 ms 25000 KB Output is correct
12 Correct 475 ms 24048 KB Output is correct
13 Correct 625 ms 30728 KB Output is correct
14 Correct 651 ms 30444 KB Output is correct
15 Correct 630 ms 30236 KB Output is correct
16 Correct 552 ms 24468 KB Output is correct
17 Correct 544 ms 25332 KB Output is correct
18 Correct 447 ms 24340 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3125 ms 180492 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 3125 ms 180492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 16392 KB Output is correct
2 Correct 225 ms 15608 KB Output is correct
3 Correct 221 ms 15448 KB Output is correct
4 Correct 224 ms 15760 KB Output is correct
5 Correct 227 ms 15652 KB Output is correct
6 Correct 219 ms 15112 KB Output is correct
7 Correct 651 ms 30332 KB Output is correct
8 Correct 643 ms 29928 KB Output is correct
9 Correct 657 ms 30880 KB Output is correct
10 Correct 570 ms 24692 KB Output is correct
11 Correct 529 ms 25000 KB Output is correct
12 Correct 475 ms 24048 KB Output is correct
13 Correct 625 ms 30728 KB Output is correct
14 Correct 651 ms 30444 KB Output is correct
15 Correct 630 ms 30236 KB Output is correct
16 Correct 552 ms 24468 KB Output is correct
17 Correct 544 ms 25332 KB Output is correct
18 Correct 447 ms 24340 KB Output is correct
19 Execution timed out 3125 ms 180492 KB Time limit exceeded
20 Halted 0 ms 0 KB -