Submission #152721

#	Time	Username	Problem	Language	Result	Execution time	Memory
152721		zeyad49	Examination (JOI19_examination)	Java	2 / 100	3125 ms	180492 KiB

examination

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 (stderr)

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

• Subtask 1: 2 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57