oj.uz

Submission #938714

# Submission time Handle Problem Language Result Execution time Memory
938714 2024-03-05T13:11:08 Z Andreibatman Street Lamps (APIO19_street_lamps) C++14
0 / 100
 104 ms 4964 KB 
#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;
    ///2*node
    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].mini++;
            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);
    tree[node].cnt=tree[2*node].cnt+tree[2*node+1].cnt;
    tree[node].mini=max(tree[node].mini,min(tree[2*node].mini,tree[2*node+1].mini));
}
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)
            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
    {
        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 {min(ans1.mini,ans2.mini),ans1.cnt+ans2.cnt};
    }
}
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')
        {
            if(sir[x]=='0')
                sir[x]='1';
            else
                sir[x]='0';
            updatelight(1,1,n,x,sir[x]-'0');
        }
        else
        {
            cin>>y;
            cout<<query(1,1,n,x,y-1).mini-1<<'\n';
        }
        updateval();
    }
    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 4964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -