#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;
struct query{
int t,u,v;
};
const int big=1000000000;
int n,q;
bool on[300010];
int last_open[300010]={};
char s[300010];
int res[300010]={};
int ans;
int seg[1200040]={};
int x,y;
vector<query> vec;
void upd(int v,int l,int r,int pos,int val)
{
if(l==r)
{
seg[v]=val;
return;
}
int mid=(l+r)>>1;
if(mid>=pos) upd(v<<1,l,mid,pos,val);
else upd(1+(v<<1),mid+1,r,pos,val);
seg[v]=max(seg[v<<1],seg[1+(v<<1)]);
}
int que(int v,int l,int r,int st,int ed)
{
if(st>ed) return -1;
if(l==st && r==ed) return seg[v];
int mid=(l+r)>>1;
return max(que(v<<1,l,mid,st,min(mid,ed)),que(1+(v<<1),mid+1,r,max(mid+1,st),ed));
}
void solve_2()
{
int temp;
for(int i=0;i<n;i++) on[i+1]=(s[i]=='1');
for(int i=0;i<q;i++)
{
if(vec[i].t==1)
{
temp=vec[i].u;
if(on[temp]) printf("%d\n",res[temp]+(i+1-last_open[temp]));
else printf("%d\n",res[temp]);
}
else
{
temp=vec[i].u;
if(on[temp])
{
on[temp]=false;
res[temp]+=((i+1)-last_open[temp]);
}
else
{
on[temp]=true;
last_open[temp]=i+1;
}
}
}
}
void solve_3()
{
for(int i=0;i<1200040;i++) seg[i]=big;
int temp,t1,t2;
for(int i=0;i<n;i++)
{
if(s[i]=='1') upd(1,1,n,i+1,0);
}
for(int i=0;i<q;i++)
{
if(vec[i].t==1)
{
t1=vec[i].u;
t2=vec[i].v;
temp=que(1,1,n,t1,t2-1);
if(temp==big) printf("0\n");
else printf("%d\n",(i+1)-temp);
}
else
{
t1=vec[i].u;
upd(1,1,n,x,i+1);
}
}
}
int main()
{
int ch=true;
scanf("%d %d",&n,&q);
scanf("%s",s);
for(int i=0;i<q;i++)
{
scanf("%s",s);
if(s[0]=='q')
{
scanf("%d %d",&x,&y);
vec.push_back({1,x,y});
if(y-x>1) ch=false;
}
else
{
scanf("%d",&x);
vec.push_back({2,x,x});
}
}
if(ch) solve_2();
else solve_3();
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | scanf("%d %d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | scanf("%s",s);
| ~~~~~^~~~~~~~
street_lamps.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | scanf("%s",s);
| ~~~~~^~~~~~~~
street_lamps.cpp:107:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | scanf("%d %d",&x,&y);
| ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:113:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | scanf("%d",&x);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
110 ms |
8404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
4940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
4940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
