#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <utility>
using namespace std;
set < pair < int , int > > how;
struct A
{
int l,r;
int nxl,nxr,nxt;
int con;
}Node[50000005];
int now=1;
char temp[15];
char all[300005];
int Find(int x,int y,int here)
{
if(here==-1) return 0;
int t;
//printf("aa %d\n",Node[here].con);
if(Node[here].nxt==-2)
{
t=Node[here].con;
if(Node[here].l==y&&Node[here].r==y) return t;
else if(y<=(Node[here].l+Node[here].r)/2) t+=Find(x,y,Node[here].nxl);
else t+=Find(x,y,Node[here].nxr);
}
else
{
t=Node[here].con;
t+=Find(x,y,Node[here].nxt);
if(Node[here].l==x&&Node[here].r==x) return t;
else if(x<=(Node[here].l+Node[here].r)/2) t+=Find(x,y,Node[here].nxl);
else t+=Find(x,y,Node[here].nxr);
}
//printf("%d %d %d %d\n",Node[here].l,Node[here].r,Node[here].nxt,t);
return t;
}
void build(int l,int r,int con,int here)
{
Node[here].l=l;
Node[here].r=r;
Node[here].nxt=con;
Node[here].nxl=-1;
Node[here].nxr=-1;
Node[here].con=0;
}
void cha(int l1,int r1,int l2,int r2,int con,int here)
{
int t;
//printf("%d %d %d %d %d %d\n",l1,r1,l2,r2,here,Node[here].nxt);
if(Node[here].nxt==-2)
{
//return ;
if(Node[here].l==l2&&Node[here].r==r2)
{
Node[here].con+=con;
return ;
}
if(Node[here].nxl==-1)
{
Node[here].nxl=now++;
build(Node[here].l,(Node[here].l+Node[here].r)/2,-2,Node[here].nxl);
}
if(Node[here].nxr==-1)
{
Node[here].nxr=now++;
build((Node[here].l+Node[here].r)/2+1,Node[here].r,-2,Node[here].nxr);
}
if(r2<=(Node[here].l+Node[here].r)/2) cha(l1,r1,l2,r2,con,Node[here].nxl);
else if(l2>(Node[here].l+Node[here].r)/2) cha(l1,r1,l2,r2,con,Node[here].nxr);
else
{
cha(l1,r1,l2,(Node[here].l+Node[here].r)/2,con,Node[here].nxl);
cha(l1,r1,(Node[here].l+Node[here].r)/2+1,r2,con,Node[here].nxr);
}
}
else
{
if(Node[here].nxt==-1)
{
Node[here].nxt=now++;
build(0,300000,-2,Node[here].nxt);
}
if(Node[here].l==l1&&Node[here].r==r1)
{
cha(l1,r1,l2,r2,con,Node[here].nxt);
return;
}
if(Node[here].nxl==-1)
{
Node[here].nxl=now++;
build(Node[here].l,(Node[here].l+Node[here].r)/2,-1,Node[here].nxl);
}
if(Node[here].nxr==-1)
{
Node[here].nxr=now++;
build((Node[here].l+Node[here].r)/2+1,Node[here].r,-1,Node[here].nxr);
}
if(r1<=(Node[here].l+Node[here].r)/2) cha(l1,r1,l2,r2,con,Node[here].nxl);
else if(l1>(Node[here].l+Node[here].r)/2) cha(l1,r1,l2,r2,con,Node[here].nxr);
else
{
cha(l1,(Node[here].l+Node[here].r)/2,l2,r2,con,Node[here].nxl);
cha((Node[here].l+Node[here].r)/2+1,r1,l2,r2,con,Node[here].nxr);
}
}
}
int main()
{
//freopen("12","rt",stdin);
//freopen("12.out","w+t",stdout);
int N,M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
scanf("%d %d",&N,&M);
//printf("%d %d\n",N,M);
scanf("%s",all+1);
build(0,300000,-1,0);
l=1;
r=0;
//printf("aaaaa\n");
for(i=1;i<=N;i++)
{
if(all[i]=='1') r=i;
else
{
if(r>=l)
{
//printf("%d %d\n",l,r);
how.insert(make_pair(l,r));
cha(l,r+1,l,r+1,M,0);
//printf("%d %d\n",l,r);
}
//if(now>=10000000) printf("%d\n",now);
l=i+1;
r=i;
}
}
//printf("aaaaa\n");
if(r>=l)
{
how.insert(make_pair(l,r));
cha(l,r+1,l,r+1,M,0);
}
//printf("aaaaa\n");
for(i=1;i<=M;i++)
{
scanf("%s",temp);
if(temp[0]=='t')
{
//printf("aa\n");
scanf("%d",&where);
if(all[where]=='0')
{
auto a=how.lower_bound(make_pair(where+1,where));
auto b=prev(a);
r1=where;
l2=where+1;
if(a==how.end()||all[where+1]=='0') r2=where+1;
else r2=a->second+1;
if(a==how.begin()||all[where-1]=='0') l1=where;
else l1=b->first;
if(r2!=where+1) how.erase(a);
if(l1!=where) how.erase(b);
if(r2-1>=l1) how.insert(make_pair(l1,r2-1));
//printf("bb %d %d %d %d\n",l1,r1,l2,r2);
//for(auto i:how) printf("aa %d %d\n",i.first,i.second);
cha(l1,r1,l2,r2,M-i,0);
}
else
{
auto a=prev(how.lower_bound(make_pair(where+1,where)));
l1=a->first;
r1=where;
l2=where+1;
r2=a->second+1;
//printf("cc %d %d\n",a->first,a->second);
how.erase(a);
if(r1-1>=l1) how.insert(make_pair(l1,r1-1));
if(r2-1>=l2) how.insert(make_pair(l2,r2-1));
//printf("cc %d %d %d %d\n",l1,r1,l2,r2);
//for(auto i:how) printf("aa %d %d\n",i.first,i.second);
//printf("%d %d %d %d\n",l1,r1,l2,r2);
cha(l1,r1,l2,r2,i-M,0);
}
all[where]=(1-(all[where]-'0'))+'0';
}
else
{
//printf("bb\n");
scanf("%d %d",&l,&r);
ok=1;
//if(how.lower_bound(make_pair(l+1,r))!=how.begin())
if(how.lower_bound(make_pair(l+1,r))!=how.begin()&&prev(how.lower_bound(make_pair(l+1,r)))->first<=l&&prev(how.lower_bound(make_pair(l+1,r)))->second>=r-1) ok=1;
else ok=0;
//for(i=l;i<r;i++) if(all[i]=='0') ok=0;
printf("%d\n",max(Find(l,r,0)-(M-i)*ok,0));
}
}
return 0;
}
Compilation message
street_lamps.cpp: In function 'void cha(int, int, int, int, int, int)':
street_lamps.cpp:53:9: warning: unused variable 't' [-Wunused-variable]
int t;
^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:117:13: warning: unused variable 't' [-Wunused-variable]
int N,M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
^
street_lamps.cpp:117:33: warning: unused variable 'j' [-Wunused-variable]
int N,M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
^
street_lamps.cpp:117:35: warning: unused variable 'k' [-Wunused-variable]
int N,M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
^
street_lamps.cpp:117:43: warning: unused variable 'ok1' [-Wunused-variable]
int N,M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
^~~
street_lamps.cpp:117:49: warning: unused variable 'ok2' [-Wunused-variable]
int N,M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
^~~
street_lamps.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&N,&M);
~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:120:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",all+1);
~~~~~^~~~~~~~~~~~
street_lamps.cpp:152:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",temp);
~~~~~^~~~~~~~~~~
street_lamps.cpp:156:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&where);
~~~~~^~~~~~~~~~~~~
street_lamps.cpp:202:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&l,&r);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
311 ms |
2792 KB |
Output is correct |
| 2 |
Correct |
343 ms |
2680 KB |
Output is correct |
| 3 |
Correct |
552 ms |
12152 KB |
Output is correct |
| 4 |
Correct |
1012 ms |
236912 KB |
Output is correct |
| 5 |
Runtime error |
402 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
55 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
896 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1152 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1280 KB |
Output is correct |
| 5 |
Correct |
747 ms |
157144 KB |
Output is correct |
| 6 |
Runtime error |
399 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
311 ms |
2792 KB |
Output is correct |
| 9 |
Correct |
343 ms |
2680 KB |
Output is correct |
| 10 |
Correct |
552 ms |
12152 KB |
Output is correct |
| 11 |
Correct |
1012 ms |
236912 KB |
Output is correct |
| 12 |
Runtime error |
402 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 13 |
Halted |
0 ms |
0 KB |
- |
