oj.uz

답안 #152792

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
152792 2019-09-09T14:06:23 Z zeyad49 Examination (JOI19_examination) Java 11
2 / 100
 3000 ms 165748 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;
			if (idx == 0)
				return 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

# 결과 실행 시간 메모리 Grader output
1 Correct 227 ms 15776 KB Output is correct
2 Correct 270 ms 15828 KB Output is correct
3 Correct 240 ms 15248 KB Output is correct
4 Correct 237 ms 15596 KB Output is correct
5 Correct 238 ms 15724 KB Output is correct
6 Correct 224 ms 15676 KB Output is correct
7 Correct 532 ms 23608 KB Output is correct
8 Correct 558 ms 24256 KB Output is correct
9 Correct 578 ms 24424 KB Output is correct
10 Correct 559 ms 24000 KB Output is correct
11 Correct 528 ms 24408 KB Output is correct
12 Correct 461 ms 24388 KB Output is correct
13 Correct 617 ms 27012 KB Output is correct
14 Correct 568 ms 26032 KB Output is correct
15 Correct 520 ms 23936 KB Output is correct
16 Correct 479 ms 22508 KB Output is correct
17 Correct 519 ms 24620 KB Output is correct
18 Correct 449 ms 23276 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3195 ms 165748 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3195 ms 165748 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 227 ms 15776 KB Output is correct
2 Correct 270 ms 15828 KB Output is correct
3 Correct 240 ms 15248 KB Output is correct
4 Correct 237 ms 15596 KB Output is correct
5 Correct 238 ms 15724 KB Output is correct
6 Correct 224 ms 15676 KB Output is correct
7 Correct 532 ms 23608 KB Output is correct
8 Correct 558 ms 24256 KB Output is correct
9 Correct 578 ms 24424 KB Output is correct
10 Correct 559 ms 24000 KB Output is correct
11 Correct 528 ms 24408 KB Output is correct
12 Correct 461 ms 24388 KB Output is correct
13 Correct 617 ms 27012 KB Output is correct
14 Correct 568 ms 26032 KB Output is correct
15 Correct 520 ms 23936 KB Output is correct
16 Correct 479 ms 22508 KB Output is correct
17 Correct 519 ms 24620 KB Output is correct
18 Correct 449 ms 23276 KB Output is correct
19 Execution timed out 3195 ms 165748 KB Time limit exceeded
20 Halted 0 ms 0 KB -