This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
using namespace std;
int n,m;
int a[1001000];
int mx[4001000];
int sum[4004000];
void upd1(int s,int e,int p,int i,int v)
{
if(i<s||i>e)
return ;
if(s==e)
{
sum[p]+=v;
return ;
}
int mid=(s+e)/2;
upd1(s,mid,p*2,i,v);
upd1(mid+1,e,p*2+1,i,v);
sum[p]=sum[p*2]+sum[p*2+1];
}
void upd2(int s,int e,int p,int i,int v)
{
if(i<s||i>e)
return ;
if(s==e)
{
mx[p]=v;
return ;
}
int mid=(s+e)/2;
upd2(s,mid,p*2,i,v);
upd2(mid+1,e,p*2+1,i,v);
mx[p]=max(mx[p*2],mx[p*2+1]);
}
int get1(int s,int e,int p,int l,int r)
{
if(s>=l&&e<=r)
return sum[p];
if(s>r||l>e)
return 0;
int mid=(s+e)/2;
return get1(s,mid,p*2,l,r)+get1(mid+1,e,p*2+1,l,r);
}
int get2(int s,int e,int p,int l,int r)
{
if(s>=l&&e<=r)
return mx[p];
if(s>r||l>e)
return 0;
int mid=(s+e)/2;
return max(get2(s,mid,p*2,l,r),get2(mid+1,e,p*2+1,l,r));
}
signed main()
{
cin>>n>>m;
string s;
cin>>s;
for(int i=0;i<n;i++)
{
if(s[i]=='1')
{
a[i]=1;
}
}
for(int i=0;i<n;i++)
upd1(0,n-1,1,i,a[i]);
for(int q=1;q<=m;q++)
{
string tt;
cin>>tt;
int x,y;
if(tt[0]=='q')
{
cin>>x>>y;
x--;
y-=2;
if(get1(0,n-1,1,x,y)!=y-x+1)
{
cout<<" "<<get1(0,n-1,1,x,y)<<" "<<get2(0,n-1,1,x,y)<<" ";
cout<<0<<endl;
continue;
}
cout<<q-get2(0,n-1,1,x,y)<<endl;
continue;
}
cin>>x;
x--;
upd1(0,n-1,1,x,1);
upd2(0,n-1,1,x,q);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |