#include<bits/stdc++.h>
#define MAX_N 100005
#define MAX_M 55
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(V) (V).begin(),(V).end()
#define reset(V) (V).clear();(V).resize(0);
#define sq(x) ((x)*(x))
#define abs(x) ((x)>0?(x):(-(x)))
#define fi first
#define se second
#define LL_inf (1LL<<60)
#define full_inf 0x7fffffff
#define half_inf 0x3fffffff
#define inf 0x3fffffff
#define MOD 1000000007
#define cpx_mod(x) (((LD)(((LL)x.real())%MOD)),((LD)(((LL)x.imag())%MOD)))
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pil;
typedef pair<LL,string> pls;
typedef complex<LD> Complex;
typedef long double LD;
struct node{
int x,y,ye,i;
};
int n,m,ans[MAX_N];
int t[4*MAX_N];
vector<node> A,B;
vector<int> X,Y,Z;
void update(int i){
int e=max({X.size(),Y.size(),Z.size()});
for(;i<=e;i+=(i&-i)) t[i]++;
return;
}
int read(int i){
int sum=0;
for(;i>0;i-=(i&-i)) sum+=t[i];
return sum;
}
int main(){
int i,x,y,z;
scanf("%d %d",&n,&m);
for(i=0;i<n;i++){
scanf("%d %d",&x,&y);
A.pb({x,y,-1,-1});X.eb(x);Y.eb(y);
B.pb({x+y,y,-1,-1});Z.eb(x+y);
}
for(i=0;i<m;i++){
scanf("%d %d %d",&x,&y,&z);
if(x+y>z){
A.pb({x,y,-1,i});X.eb(x);Y.eb(y);
}else{
A.pb({x,z-x+1,-1,i});X.eb(x);Y.eb(z-x+1);
B.pb({z,z-x,y,i});Z.eb(z);Y.eb(y);Y.eb(z-x);
}
}
sort(all(X));X.erase(unique(all(X)),X.end());
sort(all(Y));Y.erase(unique(all(Y)),Y.end());
sort(all(Z));Z.erase(unique(all(Z)),Z.end());
for(node &p:A){
p.x=X.size()-(lower_bound(all(X),p.x)-X.begin());
p.y=Y.size()-(lower_bound(all(Y),p.y)-Y.begin());
}
for(node &p:B){
p.x=Z.size()-(lower_bound(all(Z),p.x)-Z.begin());
p.y=Y.size()-(lower_bound(all(Y),p.y)-Y.begin());
p.ye=Y.size()-(lower_bound(all(Y),p.ye)-Y.begin());
}
sort(all(A),[&](const node x,const node y){return (x.x==y.x)?(x.i<y.i):(x.x<y.x);});
sort(all(B),[&](const node x,const node y){return (x.x==y.x)?(x.i<y.i):(x.x<y.x);});
for(node &p:A){
if(p.i==-1) update(p.y);
else ans[p.i]+=read(p.y);
}
for(i=max({X.size(),Y.size(),Z.size()});i>=0;i--) t[i]=0;
for(node &p:B){
if(p.i==-1) update(p.y);
else ans[p.i]+=read(p.ye)-read(p.y-1);
}
for(i=0;i<m;i++) printf("%d\n",ans[i]);
return 0;
}
Compilation message
examination.cpp: In function 'int main()':
examination.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
~~~~~^~~~~~~~~~~~~~~
examination.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x,&y);
~~~~~^~~~~~~~~~~~~~~
examination.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&x,&y,&z);
~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
10 ms |
1016 KB |
Output is correct |
8 |
Correct |
10 ms |
1016 KB |
Output is correct |
9 |
Correct |
10 ms |
1016 KB |
Output is correct |
10 |
Correct |
9 ms |
888 KB |
Output is correct |
11 |
Correct |
9 ms |
892 KB |
Output is correct |
12 |
Correct |
6 ms |
760 KB |
Output is correct |
13 |
Correct |
9 ms |
800 KB |
Output is correct |
14 |
Correct |
9 ms |
760 KB |
Output is correct |
15 |
Correct |
9 ms |
888 KB |
Output is correct |
16 |
Correct |
7 ms |
760 KB |
Output is correct |
17 |
Correct |
8 ms |
904 KB |
Output is correct |
18 |
Correct |
5 ms |
760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
272 ms |
11728 KB |
Output is correct |
2 |
Correct |
268 ms |
11704 KB |
Output is correct |
3 |
Correct |
268 ms |
11700 KB |
Output is correct |
4 |
Correct |
201 ms |
11088 KB |
Output is correct |
5 |
Correct |
209 ms |
10960 KB |
Output is correct |
6 |
Correct |
133 ms |
10568 KB |
Output is correct |
7 |
Correct |
255 ms |
11632 KB |
Output is correct |
8 |
Correct |
261 ms |
11648 KB |
Output is correct |
9 |
Correct |
246 ms |
11464 KB |
Output is correct |
10 |
Correct |
195 ms |
10704 KB |
Output is correct |
11 |
Correct |
187 ms |
11472 KB |
Output is correct |
12 |
Correct |
95 ms |
10440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
272 ms |
11728 KB |
Output is correct |
2 |
Correct |
268 ms |
11704 KB |
Output is correct |
3 |
Correct |
268 ms |
11700 KB |
Output is correct |
4 |
Correct |
201 ms |
11088 KB |
Output is correct |
5 |
Correct |
209 ms |
10960 KB |
Output is correct |
6 |
Correct |
133 ms |
10568 KB |
Output is correct |
7 |
Correct |
255 ms |
11632 KB |
Output is correct |
8 |
Correct |
261 ms |
11648 KB |
Output is correct |
9 |
Correct |
246 ms |
11464 KB |
Output is correct |
10 |
Correct |
195 ms |
10704 KB |
Output is correct |
11 |
Correct |
187 ms |
11472 KB |
Output is correct |
12 |
Correct |
95 ms |
10440 KB |
Output is correct |
13 |
Correct |
331 ms |
15244 KB |
Output is correct |
14 |
Correct |
290 ms |
13384 KB |
Output is correct |
15 |
Correct |
267 ms |
11776 KB |
Output is correct |
16 |
Correct |
262 ms |
14400 KB |
Output is correct |
17 |
Correct |
268 ms |
14352 KB |
Output is correct |
18 |
Correct |
136 ms |
11248 KB |
Output is correct |
19 |
Correct |
330 ms |
15240 KB |
Output is correct |
20 |
Correct |
312 ms |
15004 KB |
Output is correct |
21 |
Correct |
352 ms |
15948 KB |
Output is correct |
22 |
Correct |
194 ms |
10960 KB |
Output is correct |
23 |
Correct |
186 ms |
10712 KB |
Output is correct |
24 |
Correct |
95 ms |
10420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
10 ms |
1016 KB |
Output is correct |
8 |
Correct |
10 ms |
1016 KB |
Output is correct |
9 |
Correct |
10 ms |
1016 KB |
Output is correct |
10 |
Correct |
9 ms |
888 KB |
Output is correct |
11 |
Correct |
9 ms |
892 KB |
Output is correct |
12 |
Correct |
6 ms |
760 KB |
Output is correct |
13 |
Correct |
9 ms |
800 KB |
Output is correct |
14 |
Correct |
9 ms |
760 KB |
Output is correct |
15 |
Correct |
9 ms |
888 KB |
Output is correct |
16 |
Correct |
7 ms |
760 KB |
Output is correct |
17 |
Correct |
8 ms |
904 KB |
Output is correct |
18 |
Correct |
5 ms |
760 KB |
Output is correct |
19 |
Correct |
272 ms |
11728 KB |
Output is correct |
20 |
Correct |
268 ms |
11704 KB |
Output is correct |
21 |
Correct |
268 ms |
11700 KB |
Output is correct |
22 |
Correct |
201 ms |
11088 KB |
Output is correct |
23 |
Correct |
209 ms |
10960 KB |
Output is correct |
24 |
Correct |
133 ms |
10568 KB |
Output is correct |
25 |
Correct |
255 ms |
11632 KB |
Output is correct |
26 |
Correct |
261 ms |
11648 KB |
Output is correct |
27 |
Correct |
246 ms |
11464 KB |
Output is correct |
28 |
Correct |
195 ms |
10704 KB |
Output is correct |
29 |
Correct |
187 ms |
11472 KB |
Output is correct |
30 |
Correct |
95 ms |
10440 KB |
Output is correct |
31 |
Correct |
331 ms |
15244 KB |
Output is correct |
32 |
Correct |
290 ms |
13384 KB |
Output is correct |
33 |
Correct |
267 ms |
11776 KB |
Output is correct |
34 |
Correct |
262 ms |
14400 KB |
Output is correct |
35 |
Correct |
268 ms |
14352 KB |
Output is correct |
36 |
Correct |
136 ms |
11248 KB |
Output is correct |
37 |
Correct |
330 ms |
15240 KB |
Output is correct |
38 |
Correct |
312 ms |
15004 KB |
Output is correct |
39 |
Correct |
352 ms |
15948 KB |
Output is correct |
40 |
Correct |
194 ms |
10960 KB |
Output is correct |
41 |
Correct |
186 ms |
10712 KB |
Output is correct |
42 |
Correct |
95 ms |
10420 KB |
Output is correct |
43 |
Correct |
374 ms |
17936 KB |
Output is correct |
44 |
Correct |
376 ms |
17864 KB |
Output is correct |
45 |
Correct |
333 ms |
15824 KB |
Output is correct |
46 |
Correct |
289 ms |
15944 KB |
Output is correct |
47 |
Correct |
307 ms |
16320 KB |
Output is correct |
48 |
Correct |
167 ms |
13380 KB |
Output is correct |
49 |
Correct |
364 ms |
17688 KB |
Output is correct |
50 |
Correct |
397 ms |
18508 KB |
Output is correct |
51 |
Correct |
407 ms |
18924 KB |
Output is correct |
52 |
Correct |
292 ms |
16192 KB |
Output is correct |
53 |
Correct |
208 ms |
12096 KB |
Output is correct |