#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
const int L = 131072;
int n, q, ans[L];
pair<int,int> a[L];
vector<int> cpr;
vector<pair<int, pair<int,int> > > v;
vector<pair<pair<int,int>, pair<int,int> > > w;
struct seg1D {
vector<int> v, i;
void init (int X) {
i.push_back(X);
v.assign(2, 0);
}
void init (seg1D &A, seg1D &B) {
for(auto &T : A.i) i.push_back(T);
for(auto &T : B.i) i.push_back(T);
sort(i.begin(), i.end());
v.assign(i.size() * 2, 0);
}
void upd (int I, int V) {
int P = lower_bound(i.begin(), i.end(), I) - i.begin();
P += i.size();
while(P) {
v[P] += V;
P /= 2;
}
}
int get (int I) {
int S = lower_bound(i.begin(), i.end(), I) - i.begin();
int E = (int)i.size() - 1;
S += i.size(); E += i.size();
int R = 0;
while(S <= E) {
if(S%2 == 1) R += v[S++];
if(E%2 == 0) R += v[E--];
S /= 2; E /= 2;
}
return R;
}
};
struct seg2D {
seg1D v[2*L];
void init () {
for(int i=0;i<L;i++) {
v[L+i].init(i < n ? a[i].Y : 0);
}
for(int i=L;--i;) {
v[i].init(v[2*i], v[2*i+1]);
}
}
void upd (int A, int B, int V) {
A += L;
while(A) {
v[A].upd(B, V);
A /= 2;
}
}
int get (int A, int B) {
int S = A + L, E = L-1 + L;
int R = 0;
while(S <= E) {
if(S%2 == 1) R += v[S++].get(B);
if(E%2 == 0) R += v[E--].get(B);
S /= 2; E /= 2;
}
return R;
}
} seg;
int main()
{
scanf("%d%d",&n,&q);
for(int i=0;i<n;i++) {
scanf("%d%d",&a[i].X,&a[i].Y);
}
sort(a, a+n);
for(int i=0;i<n;i++) {
v.push_back({a[i].X + a[i].Y, {i, a[i].Y}});
cpr.push_back(a[i].X);
}
seg.init();
for(int i=1;i<=q;i++) {
int A, B, C;
scanf("%d%d%d",&A,&B,&C);
A = lower_bound(cpr.begin(), cpr.end(), A) - cpr.begin();
w.push_back({{C, i}, {A, B}});
}
sort(v.begin(), v.end());
sort(w.begin(), w.end());
for(int i=w.size(),j=(int)v.size()-1;i--;) {
while(j >= 0 && v[j].X >= w[i].X.X) {
seg.upd(v[j].Y.X, v[j].Y.Y, 1);
j--;
}
ans[w[i].X.Y] = seg.get(w[i].Y.X, w[i].Y.Y);
}
for(int i=1;i<=q;i++) {
printf("%d\n", ans[i]);
}
}
Compilation message
examination.cpp: In function 'int main()':
examination.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&q);
~~~~~^~~~~~~~~~~~~~
examination.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a[i].X,&a[i].Y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&A,&B,&C);
~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
112 ms |
51952 KB |
Output is correct |
2 |
Correct |
112 ms |
51952 KB |
Output is correct |
3 |
Correct |
112 ms |
51952 KB |
Output is correct |
4 |
Correct |
112 ms |
51952 KB |
Output is correct |
5 |
Correct |
113 ms |
52080 KB |
Output is correct |
6 |
Correct |
112 ms |
51872 KB |
Output is correct |
7 |
Correct |
138 ms |
52080 KB |
Output is correct |
8 |
Correct |
124 ms |
52080 KB |
Output is correct |
9 |
Correct |
129 ms |
52036 KB |
Output is correct |
10 |
Correct |
121 ms |
52080 KB |
Output is correct |
11 |
Correct |
121 ms |
52080 KB |
Output is correct |
12 |
Correct |
118 ms |
52080 KB |
Output is correct |
13 |
Correct |
124 ms |
52208 KB |
Output is correct |
14 |
Correct |
123 ms |
52252 KB |
Output is correct |
15 |
Correct |
123 ms |
52068 KB |
Output is correct |
16 |
Correct |
118 ms |
52080 KB |
Output is correct |
17 |
Correct |
121 ms |
52100 KB |
Output is correct |
18 |
Correct |
118 ms |
52080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
802 ms |
57644 KB |
Output is correct |
2 |
Correct |
848 ms |
57532 KB |
Output is correct |
3 |
Correct |
807 ms |
57732 KB |
Output is correct |
4 |
Correct |
528 ms |
57520 KB |
Output is correct |
5 |
Correct |
478 ms |
57528 KB |
Output is correct |
6 |
Correct |
298 ms |
57640 KB |
Output is correct |
7 |
Correct |
774 ms |
57744 KB |
Output is correct |
8 |
Correct |
741 ms |
57764 KB |
Output is correct |
9 |
Correct |
715 ms |
57668 KB |
Output is correct |
10 |
Correct |
359 ms |
57512 KB |
Output is correct |
11 |
Correct |
351 ms |
57468 KB |
Output is correct |
12 |
Correct |
262 ms |
57256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
802 ms |
57644 KB |
Output is correct |
2 |
Correct |
848 ms |
57532 KB |
Output is correct |
3 |
Correct |
807 ms |
57732 KB |
Output is correct |
4 |
Correct |
528 ms |
57520 KB |
Output is correct |
5 |
Correct |
478 ms |
57528 KB |
Output is correct |
6 |
Correct |
298 ms |
57640 KB |
Output is correct |
7 |
Correct |
774 ms |
57744 KB |
Output is correct |
8 |
Correct |
741 ms |
57764 KB |
Output is correct |
9 |
Correct |
715 ms |
57668 KB |
Output is correct |
10 |
Correct |
359 ms |
57512 KB |
Output is correct |
11 |
Correct |
351 ms |
57468 KB |
Output is correct |
12 |
Correct |
262 ms |
57256 KB |
Output is correct |
13 |
Correct |
889 ms |
57684 KB |
Output is correct |
14 |
Correct |
851 ms |
57540 KB |
Output is correct |
15 |
Correct |
848 ms |
57640 KB |
Output is correct |
16 |
Correct |
523 ms |
57572 KB |
Output is correct |
17 |
Correct |
524 ms |
57544 KB |
Output is correct |
18 |
Correct |
309 ms |
57636 KB |
Output is correct |
19 |
Correct |
841 ms |
57536 KB |
Output is correct |
20 |
Correct |
1010 ms |
57544 KB |
Output is correct |
21 |
Correct |
837 ms |
57532 KB |
Output is correct |
22 |
Correct |
356 ms |
57424 KB |
Output is correct |
23 |
Correct |
343 ms |
57492 KB |
Output is correct |
24 |
Correct |
255 ms |
57252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
112 ms |
51952 KB |
Output is correct |
2 |
Correct |
112 ms |
51952 KB |
Output is correct |
3 |
Correct |
112 ms |
51952 KB |
Output is correct |
4 |
Correct |
112 ms |
51952 KB |
Output is correct |
5 |
Correct |
113 ms |
52080 KB |
Output is correct |
6 |
Correct |
112 ms |
51872 KB |
Output is correct |
7 |
Correct |
138 ms |
52080 KB |
Output is correct |
8 |
Correct |
124 ms |
52080 KB |
Output is correct |
9 |
Correct |
129 ms |
52036 KB |
Output is correct |
10 |
Correct |
121 ms |
52080 KB |
Output is correct |
11 |
Correct |
121 ms |
52080 KB |
Output is correct |
12 |
Correct |
118 ms |
52080 KB |
Output is correct |
13 |
Correct |
124 ms |
52208 KB |
Output is correct |
14 |
Correct |
123 ms |
52252 KB |
Output is correct |
15 |
Correct |
123 ms |
52068 KB |
Output is correct |
16 |
Correct |
118 ms |
52080 KB |
Output is correct |
17 |
Correct |
121 ms |
52100 KB |
Output is correct |
18 |
Correct |
118 ms |
52080 KB |
Output is correct |
19 |
Correct |
802 ms |
57644 KB |
Output is correct |
20 |
Correct |
848 ms |
57532 KB |
Output is correct |
21 |
Correct |
807 ms |
57732 KB |
Output is correct |
22 |
Correct |
528 ms |
57520 KB |
Output is correct |
23 |
Correct |
478 ms |
57528 KB |
Output is correct |
24 |
Correct |
298 ms |
57640 KB |
Output is correct |
25 |
Correct |
774 ms |
57744 KB |
Output is correct |
26 |
Correct |
741 ms |
57764 KB |
Output is correct |
27 |
Correct |
715 ms |
57668 KB |
Output is correct |
28 |
Correct |
359 ms |
57512 KB |
Output is correct |
29 |
Correct |
351 ms |
57468 KB |
Output is correct |
30 |
Correct |
262 ms |
57256 KB |
Output is correct |
31 |
Correct |
889 ms |
57684 KB |
Output is correct |
32 |
Correct |
851 ms |
57540 KB |
Output is correct |
33 |
Correct |
848 ms |
57640 KB |
Output is correct |
34 |
Correct |
523 ms |
57572 KB |
Output is correct |
35 |
Correct |
524 ms |
57544 KB |
Output is correct |
36 |
Correct |
309 ms |
57636 KB |
Output is correct |
37 |
Correct |
841 ms |
57536 KB |
Output is correct |
38 |
Correct |
1010 ms |
57544 KB |
Output is correct |
39 |
Correct |
837 ms |
57532 KB |
Output is correct |
40 |
Correct |
356 ms |
57424 KB |
Output is correct |
41 |
Correct |
343 ms |
57492 KB |
Output is correct |
42 |
Correct |
255 ms |
57252 KB |
Output is correct |
43 |
Correct |
865 ms |
57512 KB |
Output is correct |
44 |
Correct |
908 ms |
57572 KB |
Output is correct |
45 |
Correct |
867 ms |
57628 KB |
Output is correct |
46 |
Correct |
552 ms |
57724 KB |
Output is correct |
47 |
Correct |
560 ms |
57544 KB |
Output is correct |
48 |
Correct |
310 ms |
57528 KB |
Output is correct |
49 |
Correct |
850 ms |
57772 KB |
Output is correct |
50 |
Correct |
862 ms |
57544 KB |
Output is correct |
51 |
Correct |
818 ms |
57616 KB |
Output is correct |
52 |
Correct |
406 ms |
57508 KB |
Output is correct |
53 |
Correct |
361 ms |
57384 KB |
Output is correct |