Submission #152791

#	Time	Username	Problem	Language	Result	Execution time	Memory
152791		zeyad49	Examination (JOI19_examination)	Java	2 / 100	3165 ms	164708 KiB

examination

import java.io.*;
import java.util.*;
import java.util.Map.Entry;

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) {
				Entry<Integer, Integer> hi = maps[idx].ceilingEntry(b);
				if (hi != null)
					ans += trees[idx].query(hi.getValue());
				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 (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