#include <bits/stdc++.h>
#define Tree int h,int l,int r
#define Left (h<<1),l,(l+r)>>1
#define Right ((h<<1)|1),((l+r)>>1)+1,r
#define pb push_back
using namespace std;
const int N=1e5+5;
int n,q,sz,res;
map < int , int > f;
vector < int > Qa,Qp,s,G[2*N],vrs[8*N],Fe[8*N];
int A[N],B[N],S[N],X[N],Y[N],Z[N],ans[N],all[8*N];
void Build(Tree) {
for (int i=l; i<=r; i++)
for (int j=0; j<G[i].size(); j++)
vrs[h].pb(G[i][j]);
sort(vrs[h].begin(),vrs[h].end());
if (l==r) return ;
Build(Left);
Build(Right);
}
void Up(int h,int idx) {
all[h]++;
while (idx<=vrs[h].size()) {
Fe[h][idx]++;
idx+=(idx & -idx);
}
}
int Ge(int h,int idx) {
res=0;
while (idx>0) {
res+=Fe[h][idx];
idx-=(idx & -idx);
}
return res;
}
inline int V(int h,int x) {
return (lower_bound(vrs[h].begin(),vrs[h].end(),x)-vrs[h].begin()+1);
}
void Upd(Tree,int id,int vl) {
if (id<l || r<id) return ;
Up(h,V(h,vl));
if (l==id && id==r) return ;
Upd(Left,id,vl);
Upd(Right,id,vl);
}
int Get(Tree,int L,int R,int vl) {
if (r<L || R<l) return 0;
if (L<=l && r<=R) return all[h]-Ge(h,V(h,vl)-1);
return Get(Left,L,R,vl)+Get(Right,L,R,vl);
}
main () {
ios::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
cin>>n>>q;
for (int i=1; i<=n; i++) {
cin>>A[i]>>B[i];
S[i]=A[i]+B[i];
s.pb(A[i]);
Qp.pb(i);
}
for (int i=1; i<=q; i++) {
cin>>X[i]>>Y[i]>>Z[i];
s.pb(X[i]);
Qa.pb(i);
}
sort(s.begin(),s.end());
for (int i=0; i<s.size(); i++) {
if (!i || s[i]!=s[i-1]) f[s[i]]=++sz;
}
sort(Qa.begin(),Qa.end(),[](int a,int b) { return Z[a]<Z[b]; } );
sort(Qp.begin(),Qp.end(),[](int a,int b) { return S[a]<S[b]; });
for (int i=1; i<=n; i++)
A[i]=f[A[i]],G[A[i]].pb(B[i]);
for (int i=1; i<=q; i++)
X[i]=f[X[i]],G[X[i]].pb(Y[i]);
Build(1,1,sz);
for (int i=1; i<=4*sz; i++) {
Fe[i].resize(vrs[i].size()+1);
}
int j=Qp.size()-1;
for (int i=Qa.size()-1; i>=0; i--) {
int id=Qa[i];
while (0<=j && Z[id]<=S[Qp[j]]) {
Upd(1,1,sz,A[Qp[j]],B[Qp[j]]);
--j;
}
ans[id]=Get(1,1,sz,X[id],sz,Y[id]);
}
for (int i=1; i<=q; i++)
cout<<ans[i]<<"\n";
}
Compilation message
examination.cpp: In function 'void Build(int, int, int)':
examination.cpp:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for (int j=0; j<G[i].size(); j++)
| ~^~~~~~~~~~~~
examination.cpp: In function 'void Up(int, int)':
examination.cpp:31:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | while (idx<=vrs[h].size()) {
| ~~~^~~~~~~~~~~~~~~
examination.cpp: At global scope:
examination.cpp:64:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
64 | main () {
| ^
examination.cpp: In function 'int main()':
examination.cpp:83:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int i=0; i<s.size(); i++) {
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
42604 KB |
Output is correct |
2 |
Correct |
28 ms |
42604 KB |
Output is correct |
3 |
Correct |
28 ms |
42604 KB |
Output is correct |
4 |
Correct |
28 ms |
42604 KB |
Output is correct |
5 |
Correct |
28 ms |
42604 KB |
Output is correct |
6 |
Correct |
29 ms |
42604 KB |
Output is correct |
7 |
Correct |
58 ms |
45212 KB |
Output is correct |
8 |
Correct |
49 ms |
45164 KB |
Output is correct |
9 |
Correct |
45 ms |
45164 KB |
Output is correct |
10 |
Correct |
43 ms |
45164 KB |
Output is correct |
11 |
Correct |
36 ms |
43244 KB |
Output is correct |
12 |
Correct |
32 ms |
43116 KB |
Output is correct |
13 |
Correct |
45 ms |
45164 KB |
Output is correct |
14 |
Correct |
46 ms |
45164 KB |
Output is correct |
15 |
Correct |
47 ms |
45120 KB |
Output is correct |
16 |
Correct |
32 ms |
43116 KB |
Output is correct |
17 |
Correct |
40 ms |
45164 KB |
Output is correct |
18 |
Correct |
31 ms |
42988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1346 ms |
100704 KB |
Output is correct |
2 |
Correct |
1249 ms |
100932 KB |
Output is correct |
3 |
Correct |
1231 ms |
100848 KB |
Output is correct |
4 |
Correct |
785 ms |
100140 KB |
Output is correct |
5 |
Correct |
289 ms |
58332 KB |
Output is correct |
6 |
Correct |
170 ms |
57308 KB |
Output is correct |
7 |
Correct |
1105 ms |
96340 KB |
Output is correct |
8 |
Correct |
1290 ms |
100676 KB |
Output is correct |
9 |
Correct |
1043 ms |
96132 KB |
Output is correct |
10 |
Correct |
182 ms |
53852 KB |
Output is correct |
11 |
Correct |
666 ms |
99808 KB |
Output is correct |
12 |
Correct |
129 ms |
54108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1346 ms |
100704 KB |
Output is correct |
2 |
Correct |
1249 ms |
100932 KB |
Output is correct |
3 |
Correct |
1231 ms |
100848 KB |
Output is correct |
4 |
Correct |
785 ms |
100140 KB |
Output is correct |
5 |
Correct |
289 ms |
58332 KB |
Output is correct |
6 |
Correct |
170 ms |
57308 KB |
Output is correct |
7 |
Correct |
1105 ms |
96340 KB |
Output is correct |
8 |
Correct |
1290 ms |
100676 KB |
Output is correct |
9 |
Correct |
1043 ms |
96132 KB |
Output is correct |
10 |
Correct |
182 ms |
53852 KB |
Output is correct |
11 |
Correct |
666 ms |
99808 KB |
Output is correct |
12 |
Correct |
129 ms |
54108 KB |
Output is correct |
13 |
Correct |
1331 ms |
101216 KB |
Output is correct |
14 |
Correct |
1324 ms |
101240 KB |
Output is correct |
15 |
Correct |
1249 ms |
100700 KB |
Output is correct |
16 |
Correct |
860 ms |
100572 KB |
Output is correct |
17 |
Correct |
312 ms |
58612 KB |
Output is correct |
18 |
Correct |
179 ms |
57308 KB |
Output is correct |
19 |
Correct |
1355 ms |
101244 KB |
Output is correct |
20 |
Correct |
1305 ms |
101420 KB |
Output is correct |
21 |
Correct |
1326 ms |
98396 KB |
Output is correct |
22 |
Correct |
176 ms |
53852 KB |
Output is correct |
23 |
Correct |
684 ms |
99840 KB |
Output is correct |
24 |
Correct |
130 ms |
53972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
42604 KB |
Output is correct |
2 |
Correct |
28 ms |
42604 KB |
Output is correct |
3 |
Correct |
28 ms |
42604 KB |
Output is correct |
4 |
Correct |
28 ms |
42604 KB |
Output is correct |
5 |
Correct |
28 ms |
42604 KB |
Output is correct |
6 |
Correct |
29 ms |
42604 KB |
Output is correct |
7 |
Correct |
58 ms |
45212 KB |
Output is correct |
8 |
Correct |
49 ms |
45164 KB |
Output is correct |
9 |
Correct |
45 ms |
45164 KB |
Output is correct |
10 |
Correct |
43 ms |
45164 KB |
Output is correct |
11 |
Correct |
36 ms |
43244 KB |
Output is correct |
12 |
Correct |
32 ms |
43116 KB |
Output is correct |
13 |
Correct |
45 ms |
45164 KB |
Output is correct |
14 |
Correct |
46 ms |
45164 KB |
Output is correct |
15 |
Correct |
47 ms |
45120 KB |
Output is correct |
16 |
Correct |
32 ms |
43116 KB |
Output is correct |
17 |
Correct |
40 ms |
45164 KB |
Output is correct |
18 |
Correct |
31 ms |
42988 KB |
Output is correct |
19 |
Correct |
1346 ms |
100704 KB |
Output is correct |
20 |
Correct |
1249 ms |
100932 KB |
Output is correct |
21 |
Correct |
1231 ms |
100848 KB |
Output is correct |
22 |
Correct |
785 ms |
100140 KB |
Output is correct |
23 |
Correct |
289 ms |
58332 KB |
Output is correct |
24 |
Correct |
170 ms |
57308 KB |
Output is correct |
25 |
Correct |
1105 ms |
96340 KB |
Output is correct |
26 |
Correct |
1290 ms |
100676 KB |
Output is correct |
27 |
Correct |
1043 ms |
96132 KB |
Output is correct |
28 |
Correct |
182 ms |
53852 KB |
Output is correct |
29 |
Correct |
666 ms |
99808 KB |
Output is correct |
30 |
Correct |
129 ms |
54108 KB |
Output is correct |
31 |
Correct |
1331 ms |
101216 KB |
Output is correct |
32 |
Correct |
1324 ms |
101240 KB |
Output is correct |
33 |
Correct |
1249 ms |
100700 KB |
Output is correct |
34 |
Correct |
860 ms |
100572 KB |
Output is correct |
35 |
Correct |
312 ms |
58612 KB |
Output is correct |
36 |
Correct |
179 ms |
57308 KB |
Output is correct |
37 |
Correct |
1355 ms |
101244 KB |
Output is correct |
38 |
Correct |
1305 ms |
101420 KB |
Output is correct |
39 |
Correct |
1326 ms |
98396 KB |
Output is correct |
40 |
Correct |
176 ms |
53852 KB |
Output is correct |
41 |
Correct |
684 ms |
99840 KB |
Output is correct |
42 |
Correct |
130 ms |
53972 KB |
Output is correct |
43 |
Correct |
1521 ms |
134112 KB |
Output is correct |
44 |
Correct |
1481 ms |
134120 KB |
Output is correct |
45 |
Correct |
1515 ms |
133984 KB |
Output is correct |
46 |
Correct |
1066 ms |
132448 KB |
Output is correct |
47 |
Correct |
326 ms |
59876 KB |
Output is correct |
48 |
Correct |
181 ms |
57180 KB |
Output is correct |
49 |
Correct |
1459 ms |
133864 KB |
Output is correct |
50 |
Correct |
1458 ms |
133852 KB |
Output is correct |
51 |
Correct |
1408 ms |
133808 KB |
Output is correct |
52 |
Correct |
204 ms |
55388 KB |
Output is correct |
53 |
Correct |
862 ms |
131424 KB |
Output is correct |