Submission #933425

# Submission time Handle Problem Language Result Execution time Memory
933425 2024-02-25T16:04:17 Z sleepntsheep Examination (JOI19_examination) C++17
0 / 100
244 ms 7992 KB
#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 -