Submission #931978

#	Time	Username	Problem	Language	Result	Execution time	Memory
931978		sleepntsheep	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	1359 ms	61656 KiB

street_lamps

#include<stdio.h>
#define N 300005
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,tune=native")

int abs(int x){return x<0?-x:x;}
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;}

#define Z (1<<20)
int f[2][N],p[1<<20][3],pn,q[1<<20][4],qn,n,Q;char s[N],op[7];
int pq[Z][4],m,ans[N],ansn[N];
int o1[N],o2[N];

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;
}

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;
    sort(o2,l,r);
    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(f[0],pq[I][2]+1);
            ansn[J]+=f_q(f[1],pq[I][2]+1);
        }
        else if(!~J&&o2[j]<m)
        {
            f_u(f[0],abs(pq[I][2])+1,pq[I][2]);
            if(pq[I][2]>=0)f_u(f[1],pq[I][2]+1,1);
            else f_u(f[1],-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(f[0],abs(pq[I][2])+1,-pq[I][2]);
            if(pq[I][2]>=0)f_u(f[1],pq[I][2]+1,-1);
            else f_u(f[1],-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<2;++i)for(int j=0;j<N;++j)f[i][j]=0;

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);compar=cmprx;
    cdq(0,m);
    for(int i=0;i<qn;++i)printf("%d\n",-ans[i]+(!!ansn[i])*q[i][2]);
}

Compilation message (stderr)

street_lamps.cpp: In function 'int cmprx(int, int)':
street_lamps.cpp:33:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   33 |     if(~pq[i][3])return 1;if(~pq[j][3])return -1;
      |     ^~
street_lamps.cpp:33:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   33 |     if(~pq[i][3])return 1;if(~pq[j][3])return -1;
      |                           ^~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:70:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 | int main(){scanf("%d%d%s",&n,&Q,s+1);
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:73:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 | for(int i=1,a,b;i<=Q;++i){scanf("%s%d",op,&a);
      |                           ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:74:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     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