This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
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, 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) {
Integer hi = maps[idx].ceilingKey(b);
if (hi != null)
ans += trees[idx].query(maps[idx].get(hi));
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.
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |