Submission #931975

#	Time	Username	Problem	Language	Result	Execution time	Memory
931975		sleepntsheep	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	1861 ms	45324 KiB

street_lamps

#include<stdio.h>
#include<stdlib.h>
#define N 300005


unsigned X=12345;int rand_(){return(X*=3)>>1;}
int (*compar)(int,int);
void sort(int*aa,int l,int r){
    while(l<r){int i=l,j=l,k=r,tmp,p=aa[l+rand_()%(r-l)];
        while(j<k)switch(compar(aa[j],p)){case 0:++j;break;case -1:tmp=aa[j],aa[j]=aa[i],aa[i]=tmp,++i,++j;break;case 1:--k,tmp=aa[j],aa[j]=aa[k],aa[k]=tmp;break;}
        sort(aa,l,i);l=k;
    }
}


void f_u(int*t,int p,int k){ for(;p<N;p+=p&-p)t[p]+=k; }
int f_q(int*t,int p){int z=0;for(;p;p-=p&-p)z+=t[p];return z;}
int f_lb(int*t,int k){if(!k)return 0;int p=0,z=0;for(int j=1<<19;j>>=1;)if(p+j<N&&z+t[p+j]<k)z+=t[p+=j];return p+1;}

int f[2][N],ff[N],fn[N],fp[N],p[1<<20][3],pn,q[1<<20][4],qn,n,Q;char s[N],op[7];
int pq[1<<21][4],m,ans[1<<18],ansp[1<<18],ansn[1<<18];
int o1[1<<21],o2[1<<21];

void A(int a,int b,int t){if(a<1)a=1;if(b>n)b=n;p[pn][0]=a,p[pn][1]=b,p[pn++][2]=t;}

int cmprb(int i,int j){return pq[i][1]<pq[j][1]?1:(pq[i][1]>pq[j][1]?-1:(~pq[i][3]&&~pq[j][3]?0:(~pq[i][3]?1:~pq[j][3]?-1:0)));
}
int cmprx(int i,int j){
    i=o1[i],j=o1[j];
    int ai=pq[i][0],aj=pq[j][0];
    if(ai-aj)return ai<aj?-1:1;
    if(~pq[i][3]&&~pq[j][3])return 0;
    if(~pq[i][3])return 1;
    if(~pq[j][3])return -1;
    return 0;
}

#include<string.h>
void cdq(int l,int r){
    if(l+1>=r)return;
    int m=(l+r)>>1;

    cdq(l,m);cdq(m,r);

    for(int j=l;j<r;++j)o2[j]=j;
    compar=cmprx;sort(o2,l,r);

    if(0){
    printf(" CDQ %d %d\n",l,r);
    for( int j=l;j<r;++j)
    {
        int I=o1[o2[j]];
        printf("        | %d %d %d %d (%c)\n",pq[I][0],pq[I][1],pq[I][2],pq[I][3],o2[j]>=m?'R':'L');
    }
    }

    for(int j=l;j<r;++j)
    {
        int I=o1[o2[j]],J=pq[I][3];
        if(~J&&o2[j]>=m){
            ans[J]+=f_q(ff,pq[I][2]+1);
            ansn[J]+=f_q(fn,pq[I][2]+1);
            ansp[J]+=f_q(fp,pq[I][2]+1);
        }
        else if(!~J&&o2[j]<m)
        {
            f_u(ff,abs(pq[I][2])+1,pq[I][2]);
            if(pq[I][2]>=0)f_u(fp,pq[I][2]+1,1);
            else f_u(fn,-pq[I][2]+1,1);
        }
    }

    for(int j=l;j<r;++j)
    {
        int I=o1[o2[j]],J=pq[I][3];
        if(!~J&&o2[j]<m)
        {
            f_u(ff,abs(pq[I][2])+1,-pq[I][2]);
            if(pq[I][2]>=0)f_u(fp,pq[I][2]+1,-1);
            else f_u(fn,-pq[I][2]+1,-1);
        }
    }

}

int main(){scanf("%d%d%s",&n,&Q,s+1);
for(int r=1;r<=n;++r)if(s[r]=='1'){int l=r;while(s[r]=='1')++r;A(l,r-1,0);}
for(int i=1;i<=n;++i)f_u(f[s[i]&1],i,1);
for(int i=1,a,b;i<=Q;++i){scanf("%s%d",op,&a);
    if(*op=='q'){scanf("%d",&b);q[qn][0]=a,q[qn][1]=--b,q[qn][2]=i;q[qn][3]=qn;++qn;}
    else{
        if(s[a]=='1')
        {
            int x=f_q(*f,a),l=f_lb(*f,x),r=f_lb(*f,x+1);
            A(l+1,r-1,-i);if(l+1<=a-1)A(l+1,a-1,i);if(a+1<=r-1)A(a+1,r-1,i);
        }
        else
        {
            int x=f_q(f[1],a),l=f_lb(f[1],x),r=f_lb(f[1],x+1);
            if(l==a-1&&a+1==r){ int X=f_q(*f,a),ll=f_lb(*f,X-1),rr=f_lb(*f,X+1);A(ll+1,a-1,-i);A(a+1,rr-1,-i);A(ll+1,rr-1,i); }
            else if(l==a-1) { int X=f_q(*f,a),ll=f_lb(*f,X-1); A(ll+1,a-1,-i);A(ll+1,a,i); }
            else if(a+1==r) { int X=f_q(*f,a),rr=f_lb(*f,X+1); A(a+1,rr-1,-i),A(a,rr-1,i); }
            else A(a,a,i);
        }
        f_u(f[s[a]&1],a,-1);s[a]^=1;f_u(f[s[a]&1],a,1);
    }
}

for(int i=0;i<pn;++i)pq[i][0]=p[i][0],pq[i][1]=p[i][1],pq[i][2]=p[i][2],pq[i][3]=-1,o1[i]=i;
for(int i=pn,j=0;j<qn;++j,++i)pq[i][0]=q[j][0],pq[i][1]=q[j][1],pq[i][2]=q[j][2],pq[i][3]=q[j][3],o1[i]=i;
m=qn+pn;
    compar=cmprb;sort(o1,0,m);
    for(int i=0;0&&i<m;++i) printf("       | %d %d %d %d\n", pq[o1[i]][0],pq[o1[i]][1],pq[o1[i]][2],pq[o1[i]][3]);
    cdq(0,m);
    for(int i=0;i<qn;++i){
        if(ansn[i]<ansp[i])ans[i]-=q[i][2];
        printf("%d\n",-ans[i]);
        //printf("  %d %d\n",ansn[i],ansp[i]);
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:86:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 | int main(){scanf("%d%d%s",&n,&Q,s+1);
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:89:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 | for(int i=1,a,b;i<=Q;++i){scanf("%s%d",op,&a);
      |                           ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:90:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     if(*op=='q'){scanf("%d",&b);q[qn][0]=a,q[qn][1]=--b,q[qn][2]=i;q[qn][3]=qn;++qn;}
      |                  ~~~~~^~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20