Submission #938892

#	Time	Username	Problem	Language	Result	Execution time	Memory
938892		Andreibatman	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	287 ms	16212 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
int n,q,i,j,ok,x,y,lazy[1200010];
char sir[300010],op[30];
struct ceva
{
    int mini,cnt;
    ceva operator +(const ceva &x)
    {
        ceva y;
        y.mini=min(x.mini,mini);
        y.cnt=x.cnt+cnt;
        return y;
    }
    bool operator ==(const ceva &x)
    {
        return mini==x.mini && cnt==x.cnt;
    }
}tree[1200010],zero;
void propag(int left,int right,int node)
{
    int mij=(left+right)/2;

    if(tree[2*node].cnt==mij-left+1)
        tree[2*node].mini+=lazy[node];
    if(tree[2*node+1].cnt==right-mij)
        tree[2*node+1].mini+=lazy[node];

    lazy[2*node]+=lazy[node];
    lazy[2*node+1]+=lazy[node];
    lazy[node]=0;
}
void updatelight(int node,int left,int right,int poz,int val)
{
    if(left!=right && lazy[node])
        propag(left,right,node);
    if(left==right)
    {
        if(val==1)
        {
            sir[left]='1';
            tree[node].cnt=1;
        }
        else
        {
            tree[node].cnt=0;
            sir[left]='0';
        }
        return;
    }
    int mij=(left+right)/2;
    if(poz<=mij)
        updatelight(2*node,left,mij,poz,val);
    else
        updatelight(2*node+1,mij+1,right,poz,val);
    int mij2=tree[node].mini;
    tree[node]=tree[2*node]+tree[2*node+1];
    tree[node].mini=max(tree[node].mini,mij2);
}
void updateval()
{
    if(tree[1].cnt==n)
        tree[1].mini++;
    lazy[1]++;
}
ceva query(int node,int left,int right,int st,int dr)
{
    if(left!=right && lazy[node])
        propag(left,right,node);
    if(st<=left && right<=dr)
    {
        if(tree[node].cnt!=right-left+1 && st==dr)
            return zero;
        return tree[node];
    }
    int mij=(left+right)/2;
    ceva ans1=zero,ans2=zero;
    if(st<=mij && mij>=dr)
        return query(2*node,left,mij,st,dr);
    else if(st>mij && mij<dr)
        return query(2*node+1,mij+1,right,st,dr);
    else if(st<=mij && mij<dr)
    {
        ans1=query(2*node,left,mij,st,dr);
        ans2=query(2*node+1,mij+1,right,st,dr);
        if(ans1==zero || ans2==zero)
            return zero;
        return ans1+ans2;
    }
    return zero;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q>>(sir+1);
    for(i=1;i<=n;i++)
        updatelight(1,1,n,i,sir[i]-'0');
    updateval();
    while(q--)
    {
        cin>>op>>x;
        if(op[0]=='t')
            updatelight(1,1,n,x,1-sir[x]+'0');
        else
        {
            cin>>y;
            cout<<query(1,1,n,x,y-1).mini<<'\n';
        }
        updateval();
    }
    return 0;
}

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