oj.uz

Submission #152791

# Submission time Handle Problem Language Result Execution time Memory
152791 2019-09-09T14:05:17 Z zeyad49 Examination (JOI19_examination) Java 11
2 / 100
 3000 ms 164708 KB 
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

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 231 ms 15540 KB Output is correct
2 Correct 219 ms 15312 KB Output is correct
3 Correct 211 ms 15252 KB Output is correct
4 Correct 227 ms 15304 KB Output is correct
5 Correct 224 ms 15752 KB Output is correct
6 Correct 223 ms 14904 KB Output is correct
7 Correct 573 ms 24828 KB Output is correct
8 Correct 540 ms 24920 KB Output is correct
9 Correct 544 ms 23684 KB Output is correct
10 Correct 533 ms 23996 KB Output is correct
11 Correct 552 ms 24448 KB Output is correct
12 Correct 499 ms 21900 KB Output is correct
13 Correct 549 ms 23832 KB Output is correct
14 Correct 534 ms 23896 KB Output is correct
15 Correct 561 ms 25556 KB Output is correct
16 Correct 477 ms 24464 KB Output is correct
17 Correct 516 ms 20560 KB Output is correct
18 Correct 445 ms 23900 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 15540 KB Output is correct
2 Correct 219 ms 15312 KB Output is correct
3 Correct 211 ms 15252 KB Output is correct
4 Correct 227 ms 15304 KB Output is correct
5 Correct 224 ms 15752 KB Output is correct
6 Correct 223 ms 14904 KB Output is correct
7 Correct 573 ms 24828 KB Output is correct
8 Correct 540 ms 24920 KB Output is correct
9 Correct 544 ms 23684 KB Output is correct
10 Correct 533 ms 23996 KB Output is correct
11 Correct 552 ms 24448 KB Output is correct
12 Correct 499 ms 21900 KB Output is correct
13 Correct 549 ms 23832 KB Output is correct
14 Correct 534 ms 23896 KB Output is correct
15 Correct 561 ms 25556 KB Output is correct
16 Correct 477 ms 24464 KB Output is correct
17 Correct 516 ms 20560 KB Output is correct
18 Correct 445 ms 23900 KB Output is correct
19 Execution timed out 3165 ms 164708 KB Time limit exceeded
20 Halted 0 ms 0 KB -