oj.uz

Submission #938898

# Submission time Handle Problem Language Result Execution time Memory
938898 2024-03-05T19:11:04 Z Andreibatman Street Lamps (APIO19_street_lamps) C++14
40 / 100
 268 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];
}
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');
    while(q--)
    {
        updateval();
        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';

        }

    }
    return 0;
}

Compilation message

street_lamps.cpp: In function 'void updatelight(int, int, int, int, int)':
street_lamps.cpp:56:9: warning: unused variable 'mij2' [-Wunused-variable]
   56 |     int mij2=tree[node].mini;
      |         ^~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2548 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 73 ms 3220 KB Output is correct
2 Correct 82 ms 3408 KB Output is correct
3 Correct 100 ms 3408 KB Output is correct
4 Correct 185 ms 14948 KB Output is correct
5 Correct 192 ms 15404 KB Output is correct
6 Correct 160 ms 14672 KB Output is correct
7 Correct 171 ms 14816 KB Output is correct
8 Correct 190 ms 16068 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 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 149 ms 14236 KB Output is correct
6 Correct 190 ms 14420 KB Output is correct
7 Correct 268 ms 14436 KB Output is correct
8 Correct 259 ms 16212 KB Output is correct
9 Correct 76 ms 3152 KB Output is correct
10 Correct 83 ms 3152 KB Output is correct
11 Correct 84 ms 3408 KB Output is correct
12 Correct 266 ms 14896 KB Output is correct
13 Correct 262 ms 16000 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 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 2548 KB Output isn't correct
2 Halted 0 ms 0 KB -