oj.uz

Submission #931975

# Submission time Handle Problem Language Result Execution time Memory
931975 2024-02-22T17:15:43 Z sleepntsheep Street Lamps (APIO19_street_lamps) C++17
20 / 100
 1861 ms 45324 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 10668 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 786 ms 36956 KB Output is correct
2 Correct 817 ms 37184 KB Output is correct
3 Correct 928 ms 37968 KB Output is correct
4 Correct 1495 ms 42472 KB Output is correct
5 Correct 1601 ms 45324 KB Output is correct
6 Correct 1584 ms 44244 KB Output is correct
7 Incorrect 700 ms 34932 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12636 KB Output is correct
2 Correct 5 ms 12636 KB Output is correct
3 Correct 5 ms 12636 KB Output is correct
4 Correct 3 ms 8804 KB Output is correct
5 Correct 1637 ms 42528 KB Output is correct
6 Correct 1861 ms 43612 KB Output is correct
7 Correct 1762 ms 44552 KB Output is correct
8 Incorrect 988 ms 38388 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 4 ms 10844 KB Output is correct
3 Correct 4 ms 11100 KB Output is correct
4 Correct 5 ms 12636 KB Output is correct
5 Incorrect 1286 ms 37196 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 10668 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 786 ms 36956 KB Output is correct
9 Correct 817 ms 37184 KB Output is correct
10 Correct 928 ms 37968 KB Output is correct
11 Correct 1495 ms 42472 KB Output is correct
12 Correct 1601 ms 45324 KB Output is correct
13 Correct 1584 ms 44244 KB Output is correct
14 Incorrect 700 ms 34932 KB Output isn't correct
15 Halted 0 ms 0 KB -