oj.uz

Submission #713605

# Submission time Handle Problem Language Result Execution time Memory
713605 2023-03-22T15:58:32 Z bin9638 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 1329 ms 141988 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define N 300010
#define ii pair<int,int>
#define fs first
#define sc second
#define ld double

int n,q,a[N];

struct PIT
{
    int goc[N]={},dem=0;

    void init()
    {
        goc[0]=1;
        dem=1;
    }

    struct node
    {
        int l_child=0,r_child=0,sum=0;
    }ST[N*42];

    int update(int l,int r,int i,int val,int oldId)
    {
        if(l>i||r<i)
            return oldId;
        if(l==r)
        {
            dem++;
            ST[dem].sum=val;
            return dem;
        }
        int mid=(l+r)/2,cur=++dem;
        ST[cur].l_child=update(l,mid,i,val,ST[oldId].l_child);
        ST[cur].r_child=update(mid+1,r,i,val,ST[oldId].r_child);
        ST[cur].sum=(ST[ST[cur].l_child].sum+ST[ST[cur].r_child].sum);
        return cur;
    }

    int get(int id,int l,int r,int u,int v)
    {
        if(l>v||r<u)
            return 0;
        if(l>=u&&r<=v)
            return ST[id].sum;
        int mid=(l+r)/2;
        return get(ST[id].l_child,l,mid,u,v)+get(ST[id].r_child,mid+1,r,u,v);
    }
}T;

int main()
{
    #ifdef SKY
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    #endif // SKY
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        char ch;
        cin>>ch;
        a[i]=ch-'0';
    }
    T.init();
    for(int i=1;i<=n;i++)
        T.goc[0]=T.update(1,n,i,a[i],T.goc[0]);
    for(int t=1;t<=q;t++)
    {
        string type;
        cin>>type;
        if(type=="toggle")
        {
            int vt;
            cin>>vt;
            T.goc[t]=T.update(1,n,vt,1,T.goc[t-1]);
        }else
        {
            T.goc[t]=T.goc[t-1];
            int l=0,r=t-1,res=t,u,v;
            cin>>u>>v;
            v--;
            while(l<=r)
            {
                int mid=(l+r)/2;
                if(T.get(T.goc[mid],1,n,u,v)==v-u+1)
                {
                    res=mid;
                    r=mid-1;
                }else
                    l=mid+1;
            }
            cout<<t-res<<"\n";
        }
    }
    return 0;
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 183 ms 19144 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 596 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 344 ms 141988 KB Output is correct
6 Correct 831 ms 122932 KB Output is correct
7 Correct 1203 ms 103180 KB Output is correct
8 Correct 1229 ms 78400 KB Output is correct
9 Correct 279 ms 4908 KB Output is correct
10 Correct 337 ms 5212 KB Output is correct
11 Correct 330 ms 5452 KB Output is correct
12 Correct 1329 ms 77132 KB Output is correct
13 Correct 1318 ms 78300 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Incorrect 2 ms 468 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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -