#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, d = 0, q, x[100005], y[100005], z[100005], cnt[200005];
bool mark[500005], Q[500005];
set<int> s;
struct NODE {
int x, y, z, idx;
bool operator < (NODE b) {
if(x != b.x) return x < b.x;
else if(y != b.y) return y < b.y;
else if(z != b.z) return z < b.z;
else return idx > b.idx;
}
} node[500005];
int bit[500005];
void update(int pos, int val) {
while(pos <= d) {
bit[pos] += val;
pos += pos & -pos;
}
}
int get(int pos) {
int res = 0;
while(pos > 0) {
res += bit[pos];
pos -= pos & -pos;
}
return res;
}
int range(int l, int r) {
return get(r) - get(l-1);
}
void cdq(int l, int r) {
int mid = (l + r) / 2;
if(l == r) return;
cdq(l, mid);
cdq(mid + 1, r);
for (int i = mid + 1; i <= r; i++) {
if(!Q[node[i].idx]) update(node[i].z, 1);
}
vector<NODE> v;
int p1;
p1 = mid+1;
for (int i = l; i <= mid; i++) {
while(p1 <= r && node[p1].y <= node[i].y) {
v.push_back(node[p1]);
if(!Q[node[p1].idx]) update(node[p1].z, -1);
p1++;
}
v.push_back(node[i]);
cnt[node[i].idx] += range(node[i].z+1, d);
}
while(p1 <= r) {
v.push_back(node[p1]);
if(!Q[node[p1].idx]) update(node[p1].z, -1);
p1++;
}
for (int i = l; i <= r; i++) {
node[i] = v[i-l];
}
return;
}
map<int, int> mp;
signed main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> node[i].x >> node[i].y;
node[i].z = node[i].x + node[i].y;
s.insert(node[i].x);
s.insert(node[i].y);
s.insert(node[i].z);
node[i].idx = i;
}
for (int i = 1; i <= q; i++) {
cin >> x[i] >> y[i] >> z[i];
y[i]--, z[i]--;
s.insert(x[i]);
s.insert(y[i]);
s.insert(z[i]);
}
for (int i: s) mp[i] = ++d;
for (int i = 1; i <= n; i++) {
node[i].x = mp[node[i].x];
node[i].y = mp[node[i].y];
node[i].z = mp[node[i].z];
//cout << node[i].x << ' ' << node[i].y << ' ' << node[i].z << '\n';
}
for (int i = 1; i <= q; i++) {
x[i] = mp[x[i]];
y[i] = mp[y[i]];
z[i] = mp[z[i]];
node[i+n] = {x[i], y[i], z[i], i + n};
Q[i+n] = true;
}
sort(node + 1, node + 1 + q + n);
cdq(1, n+q);
for (int i = 1; i <= q; i++) {
cout << cnt[i+n] << '\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6488 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
17 ms |
9172 KB |
Output is correct |
8 |
Correct |
16 ms |
9116 KB |
Output is correct |
9 |
Correct |
17 ms |
9084 KB |
Output is correct |
10 |
Correct |
12 ms |
8264 KB |
Output is correct |
11 |
Correct |
12 ms |
8348 KB |
Output is correct |
12 |
Correct |
8 ms |
7068 KB |
Output is correct |
13 |
Correct |
14 ms |
8756 KB |
Output is correct |
14 |
Correct |
13 ms |
8736 KB |
Output is correct |
15 |
Correct |
14 ms |
8736 KB |
Output is correct |
16 |
Correct |
8 ms |
7652 KB |
Output is correct |
17 |
Correct |
14 ms |
7972 KB |
Output is correct |
18 |
Correct |
6 ms |
7068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
478 ms |
43608 KB |
Output is correct |
2 |
Correct |
514 ms |
43908 KB |
Output is correct |
3 |
Correct |
465 ms |
45748 KB |
Output is correct |
4 |
Correct |
354 ms |
40108 KB |
Output is correct |
5 |
Correct |
358 ms |
40028 KB |
Output is correct |
6 |
Correct |
157 ms |
28744 KB |
Output is correct |
7 |
Correct |
454 ms |
44196 KB |
Output is correct |
8 |
Correct |
479 ms |
45388 KB |
Output is correct |
9 |
Correct |
461 ms |
43096 KB |
Output is correct |
10 |
Correct |
353 ms |
39108 KB |
Output is correct |
11 |
Correct |
316 ms |
39856 KB |
Output is correct |
12 |
Correct |
132 ms |
28720 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
478 ms |
43608 KB |
Output is correct |
2 |
Correct |
514 ms |
43908 KB |
Output is correct |
3 |
Correct |
465 ms |
45748 KB |
Output is correct |
4 |
Correct |
354 ms |
40108 KB |
Output is correct |
5 |
Correct |
358 ms |
40028 KB |
Output is correct |
6 |
Correct |
157 ms |
28744 KB |
Output is correct |
7 |
Correct |
454 ms |
44196 KB |
Output is correct |
8 |
Correct |
479 ms |
45388 KB |
Output is correct |
9 |
Correct |
461 ms |
43096 KB |
Output is correct |
10 |
Correct |
353 ms |
39108 KB |
Output is correct |
11 |
Correct |
316 ms |
39856 KB |
Output is correct |
12 |
Correct |
132 ms |
28720 KB |
Output is correct |
13 |
Correct |
642 ms |
47336 KB |
Output is correct |
14 |
Correct |
556 ms |
44800 KB |
Output is correct |
15 |
Correct |
505 ms |
43912 KB |
Output is correct |
16 |
Correct |
478 ms |
39124 KB |
Output is correct |
17 |
Correct |
419 ms |
40400 KB |
Output is correct |
18 |
Correct |
188 ms |
28144 KB |
Output is correct |
19 |
Correct |
585 ms |
46660 KB |
Output is correct |
20 |
Correct |
560 ms |
46648 KB |
Output is correct |
21 |
Correct |
561 ms |
47652 KB |
Output is correct |
22 |
Correct |
299 ms |
39200 KB |
Output is correct |
23 |
Correct |
309 ms |
37572 KB |
Output is correct |
24 |
Correct |
136 ms |
28404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6488 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
17 ms |
9172 KB |
Output is correct |
8 |
Correct |
16 ms |
9116 KB |
Output is correct |
9 |
Correct |
17 ms |
9084 KB |
Output is correct |
10 |
Correct |
12 ms |
8264 KB |
Output is correct |
11 |
Correct |
12 ms |
8348 KB |
Output is correct |
12 |
Correct |
8 ms |
7068 KB |
Output is correct |
13 |
Correct |
14 ms |
8756 KB |
Output is correct |
14 |
Correct |
13 ms |
8736 KB |
Output is correct |
15 |
Correct |
14 ms |
8736 KB |
Output is correct |
16 |
Correct |
8 ms |
7652 KB |
Output is correct |
17 |
Correct |
14 ms |
7972 KB |
Output is correct |
18 |
Correct |
6 ms |
7068 KB |
Output is correct |
19 |
Correct |
478 ms |
43608 KB |
Output is correct |
20 |
Correct |
514 ms |
43908 KB |
Output is correct |
21 |
Correct |
465 ms |
45748 KB |
Output is correct |
22 |
Correct |
354 ms |
40108 KB |
Output is correct |
23 |
Correct |
358 ms |
40028 KB |
Output is correct |
24 |
Correct |
157 ms |
28744 KB |
Output is correct |
25 |
Correct |
454 ms |
44196 KB |
Output is correct |
26 |
Correct |
479 ms |
45388 KB |
Output is correct |
27 |
Correct |
461 ms |
43096 KB |
Output is correct |
28 |
Correct |
353 ms |
39108 KB |
Output is correct |
29 |
Correct |
316 ms |
39856 KB |
Output is correct |
30 |
Correct |
132 ms |
28720 KB |
Output is correct |
31 |
Correct |
642 ms |
47336 KB |
Output is correct |
32 |
Correct |
556 ms |
44800 KB |
Output is correct |
33 |
Correct |
505 ms |
43912 KB |
Output is correct |
34 |
Correct |
478 ms |
39124 KB |
Output is correct |
35 |
Correct |
419 ms |
40400 KB |
Output is correct |
36 |
Correct |
188 ms |
28144 KB |
Output is correct |
37 |
Correct |
585 ms |
46660 KB |
Output is correct |
38 |
Correct |
560 ms |
46648 KB |
Output is correct |
39 |
Correct |
561 ms |
47652 KB |
Output is correct |
40 |
Correct |
299 ms |
39200 KB |
Output is correct |
41 |
Correct |
309 ms |
37572 KB |
Output is correct |
42 |
Correct |
136 ms |
28404 KB |
Output is correct |
43 |
Incorrect |
1089 ms |
94840 KB |
Output isn't correct |
44 |
Halted |
0 ms |
0 KB |
- |