oj.uz

Submission #938892

# Submission time Handle Problem Language Result Execution time Memory
938892 2024-03-05T18:53:58 Z Andreibatman Street Lamps (APIO19_street_lamps) C++14
20 / 100
 287 ms 16212 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;

    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.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 72 ms 3004 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 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 167 ms 14164 KB Output is correct
6 Correct 202 ms 14400 KB Output is correct
7 Correct 260 ms 14424 KB Output is correct
8 Correct 287 ms 16212 KB Output is correct
9 Correct 77 ms 3152 KB Output is correct
10 Correct 88 ms 3240 KB Output is correct
11 Correct 86 ms 3412 KB Output is correct
12 Correct 281 ms 15168 KB Output is correct
13 Correct 263 ms 16088 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 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 -