oj.uz

Submission #938716

# Submission time Handle Problem Language Result Execution time Memory
938716 2024-03-05T13:11:43 Z Andreibatman Street Lamps (APIO19_street_lamps) C++14
20 / 100
 297 ms 22116 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<<max(0,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 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2524 KB Output is correct
3 Correct 1 ms 2528 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 170 ms 18444 KB Output is correct
6 Correct 201 ms 19168 KB Output is correct
7 Correct 248 ms 19668 KB Output is correct
8 Correct 278 ms 22116 KB Output is correct
9 Correct 79 ms 6164 KB Output is correct
10 Correct 86 ms 6228 KB Output is correct
11 Correct 89 ms 6628 KB Output is correct
12 Correct 267 ms 20560 KB Output is correct
13 Correct 297 ms 22096 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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