#include <stdio.h>
unsigned X=12345;int rand_(){return(X*=3)>>1;}
int (*compar)(int,int);void sort(int*a,int l,int r){
while(l<r){int i=l,j=l,k=r,t,p=a[l+rand_()%(r-l)];
while(j<k)switch(compar(a[j],p)){case 0:++j;break;case -1:t=a[j],a[j]=a[i],a[i]=t,++i,++j;break;case 1:t=a[--k],a[k]=a[j],a[j]=t;break;}sort(a,l,i);l=k;}
}
int n,q,a[200000][4],z[100000],o1[200000],o2[200000],ff[200002];
void _u(int p,int k){for(;p;p-=p&-p)ff[p]+=k;}
int _q(int p){int z=0;for(;p<=200001;p+=p&-p)z+=ff[p];return z;}
int cmp(int i,int j){return i>j?1:(i<j?-1:0);}
int shinlena(int i,int j){return a[i][0]>a[j][0]?-1:a[i][0]<a[j][0]?1:
(~a[i][3]&&~a[j][3]?0:(~a[i][3]?1:~a[j][3]?1:0));}
int doppy(int i,int j){return a[i][1]>a[j][1]?-1:a[i][1]<a[j][1]?1:
(~a[i][3]&&~a[j][3]?0:(~a[i][3]?1:~a[j][3]?1:0));}
void cdq(int l, int r)
{
if(l>=r)return;
int m=(l+r)/2,p0=l,p1=m+1,p2=l;cdq(l,m);cdq(m+1,r);
while(p0<=m&&p1<=r)
if(!~doppy(o1[p0],o1[p1]))o2[p2++]=p0++;
else o2[p2++]=p1++;
while(p0<=m)o2[p2++]=p0++;
while(p1<=r)o2[p2++]=p1++;
for(int jjj,jj,I,j=l;j<=r;++j){jjj=o1[jj=o2[j]];
if((~(I=a[jjj][3]))&&jj>m)z[I]+=_q(a[jjj][2]);
else if(!~I&&jj<=m)_u(a[jjj][2],1);
}
for(int jjj,jj,j=l;j<=r;++j){jjj=o1[jj=o2[j]];
if(!~a[jjj][3]&&jj<=m)_u(a[jjj][2],-1); }
for(int j=l;j<=r;++j)o2[j]=o1[o2[j]];
for(int j=l;j<=r;++j)o1[j]=o2[j];
}
int c[400000],C=1;
int main()
{
scanf("%d%d",&n,&q);
for(int i=0;i<n;++i)scanf("%d%d",a[i],a[i]+1),a[i][2]=a[i][0]+a[i][1],a[i][3]=-1,o1[i]=o2[i]=i,c[C++]=a[i][2];
for(int j=n,i=0;i<q;++j,++i)scanf("%d%d%d",a[j],a[j]+1,a[j]+2),a[j][3]=i,o1[j]=o2[j]=j,c[C++]=a[j][2];
compar=cmp;sort(c,1,C);
for(int z=-2,l,r,i=0;i<n+q;++i){l=1,r=C-1;
while(l<=r){int yy=(l+r)/2;if(c[yy]<a[i][2])l=yy+1;else r=yy-1,z=yy;}a[i][2]=z;
}
compar=shinlena;sort(o1,0,n+q);
cdq(0,n+q-1);
for(int i=0;i<q;++i)printf("%d\n",z[i]);
}
Compilation message
examination.cpp: In function 'void sort(int*, int, int)':
examination.cpp:6:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
6 | while(j<k)switch(compar(a[j],p)){case 0:++j;break;case -1:t=a[j],a[j]=a[i],a[i]=t,++i,++j;break;case 1:t=a[--k],a[k]=a[j],a[j]=t;break;}sort(a,l,i);l=k;}
| ^~~~~
examination.cpp:6:145: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
6 | while(j<k)switch(compar(a[j],p)){case 0:++j;break;case -1:t=a[j],a[j]=a[i],a[i]=t,++i,++j;break;case 1:t=a[--k],a[k]=a[j],a[j]=t;break;}sort(a,l,i);l=k;}
| ^~~~
examination.cpp: In function 'int main()':
examination.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | scanf("%d%d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~
examination.cpp:42:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | for(int i=0;i<n;++i)scanf("%d%d",a[i],a[i]+1),a[i][2]=a[i][0]+a[i][1],a[i][3]=-1,o1[i]=o2[i]=i,c[C++]=a[i][2];
| ~~~~~^~~~~~~~~~~~~~~~~~~~
examination.cpp:43:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | for(int j=n,i=0;i<q;++j,++i)scanf("%d%d%d",a[j],a[j]+1,a[j]+2),a[j][3]=i,o1[j]=o2[j]=j,c[C++]=a[j][2];
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 7 |
Correct |
7 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
9 ms |
4552 KB |
Output is correct |
| 9 |
Correct |
7 ms |
4444 KB |
Output is correct |
| 10 |
Incorrect |
7 ms |
4444 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
244 ms |
7992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
244 ms |
7992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 7 |
Correct |
7 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
9 ms |
4552 KB |
Output is correct |
| 9 |
Correct |
7 ms |
4444 KB |
Output is correct |
| 10 |
Incorrect |
7 ms |
4444 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
