oj.uz

Submission #938891

# Submission time Handle Problem Language Result Execution time Memory
938891 2024-03-05T18:53:09 Z Andreibatman Street Lamps (APIO19_street_lamps) C++14
40 / 100
 292 ms 22352 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)
        //    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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3272 KB Output is correct
2 Correct 92 ms 7260 KB Output is correct
3 Correct 101 ms 7508 KB Output is correct
4 Correct 180 ms 19860 KB Output is correct
5 Correct 191 ms 20456 KB Output is correct
6 Correct 178 ms 19856 KB Output is correct
7 Correct 179 ms 20560 KB Output is correct
8 Correct 188 ms 22352 KB Output is correct

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 2396 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 161 ms 14228 KB Output is correct
6 Correct 204 ms 14280 KB Output is correct
7 Correct 292 ms 14552 KB Output is correct
8 Correct 273 ms 16208 KB Output is correct
9 Correct 76 ms 3292 KB Output is correct
10 Correct 81 ms 3284 KB Output is correct
11 Correct 84 ms 3316 KB Output is correct
12 Correct 284 ms 14688 KB Output is correct
13 Correct 260 ms 16064 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 Correct 1 ms 2396 KB Output is correct
3 Incorrect 1 ms 2524 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 -