#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
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;}
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
10588 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10588 KB |
Output is correct |
| 3 |
Correct |
1 ms |
10588 KB |
Output is correct |
| 4 |
Correct |
2 ms |
10588 KB |
Output is correct |
| 5 |
Correct |
2 ms |
10588 KB |
Output is correct |
| 6 |
Correct |
1 ms |
10588 KB |
Output is correct |
| 7 |
Correct |
1 ms |
10588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
817 ms |
29536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
10588 KB |
Output is correct |
| 2 |
Correct |
5 ms |
10588 KB |
Output is correct |
| 3 |
Correct |
5 ms |
10588 KB |
Output is correct |
| 4 |
Correct |
2 ms |
10736 KB |
Output is correct |
| 5 |
Runtime error |
1359 ms |
61656 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10588 KB |
Output is correct |
| 2 |
Correct |
4 ms |
10588 KB |
Output is correct |
| 3 |
Correct |
4 ms |
10588 KB |
Output is correct |
| 4 |
Correct |
4 ms |
10588 KB |
Output is correct |
| 5 |
Incorrect |
1235 ms |
27848 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
10588 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10588 KB |
Output is correct |
| 3 |
Correct |
1 ms |
10588 KB |
Output is correct |
| 4 |
Correct |
2 ms |
10588 KB |
Output is correct |
| 5 |
Correct |
2 ms |
10588 KB |
Output is correct |
| 6 |
Correct |
1 ms |
10588 KB |
Output is correct |
| 7 |
Correct |
1 ms |
10588 KB |
Output is correct |
| 8 |
Incorrect |
817 ms |
29536 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
