제출 #933412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
933412		sleepntsheep	Examination (JOI19_examination)	C++17	0 / 100	230 ms	6784 KiB

examination

#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 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]+1);
        else if(!~I&&jj<=m)_u(a[jjj][2]+1,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,-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 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;
    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;
    compar=shinlena;sort(o1,0,n+q);
    cdq(0,n+q-1);
    for(int i=0;i<q;++i)printf("%d\n",z[i]);
}

컴파일 시 표준 에러 (stderr) 메시지

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:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d%d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~
examination.cpp:40:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     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;
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~
examination.cpp:41:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     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;
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57