Submission #551341

#	Time	Username	Problem	Language	Result	Execution time	Memory
551341		ala2	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	403 ms	1640 KiB

street_lamps

#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]=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--;
            if(get1(0,n-1,1,x,y)!=y-x+1)
            {
                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);
    }
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20