oj.uz

Submission #971885

# Submission time Handle Problem Language Result Execution time Memory
971885 2024-04-29T12:44:31 Z vivkostov Street Lamps (APIO19_street_lamps) C++14
40 / 100
 97 ms 22152 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    /*#ifdef ONLINE_JUDGE
    freopen("taxi.in", "r", stdin);
    freopen("taxi.out", "w", stdout);
    #endif
    */
}
int n,q;
string s[305];
string a[300005];
int l[300005],r[300005],safe[2000005],last[2000005],state[2000005],lazy[2000005];
int answer(int l,int r,int ti)
{
    int br=0;
    for(int i=0; i<ti; i++)
    {
        for(int j=l; j<r; j++)
        {
            if(s[i][j]=='0')break;
            if(j==r-1)br++;
        }
    }
    return br;
}
void build_tree(int l,int r,int h)
{
    if(l==r)
    {
        if(s[0][l-1]=='1')
        {
            state[h]=1;
        }
        return;
    }
    int m=(l+r)/2;
    build_tree(l,m,h*2);
    build_tree(m+1,r,h*2+1);
    if(state[h*2]&&state[h*2+1])state[h]=1;
}
void update(int l,int r,int q,int h,int ti)
{
    if(l>q||r<q)return;
    if(l==r)
    {
        state[h]=1;
        last[h]=ti;
        return;
    }
    int m=(l+r)/2;
    update(l,m,q,h*2,ti);
    update(m+1,r,q,h*2+1,ti);
    if(state[h*2]&&state[h*2+1])
    {
        state[h]=1;
        last[h]=max(last[h*2],last[h*2+1]);
    }
}
int query(int l,int r,int ql,int qr,int h,int ti)
{
    if(l>qr||r<ql)return 10000000;
    if(l>=ql&&r<=qr)
    {
        if(!state[h])return 0;
        else return ti-last[h];
    }
    int m=(l+r)/2;
    return min(query(l,m,ql,qr,h*2,ti),query(m+1,r,ql,qr,h*2+1,ti));
}
void check(int l,int r,int h)
{
    cout<<l<<" "<<r<<" "<<last[h]<<" "<<state[h]<<endl;
    if(l==r)return;
    int m=(l+r)/2;
    check(l,m,h*2);
    check(m+1,r,h*2+1);
}
void read()
{
    cin>>n>>q>>s[0];
    if(n<=100&&q<=100)
    {
        for(int i=1; i<=q; i++)
        {
            cin>>a[i]>>l[i];
            l[i]--;
            s[i]=s[i-1];
            if(a[i]=="query")
            {
                cin>>r[i];
                r[i]--;
                cout<<answer(l[i],r[i],i)<<endl;
            }
            else
            {
                s[i][l[i]]++;
                if(s[i][l[i]]=='2')s[i][l[i]]='0';
            }
        }
    }
    else
    {
        int h=0;
        for(int i=0; i<n; i++)
        {
            if(s[0][i]=='1')state[i]=1;
        }
        for(int i=1; i<=q; i++)
        {
            cin>>a[i]>>l[i];
            l[i]--;
            if(a[i]=="toggle");
            else
            {
                cin>>r[i];
                if(r[i]-l[i]!=2)h=1;
            }
        }
        if(!h)
        {
            for(int i=1; i<=q; i++)
            {
                if(a[i]=="toggle")
                {
                    if(state[l[i]]==1)safe[l[i]]+=i-last[l[i]];
                    last[l[i]]=i;
                    state[l[i]]=(state[l[i]]+1)%2;
                }
                else
                {
                    cout<<safe[l[i]]+(i-last[l[i]])*state[l[i]]<<endl;
                }
            }
        }
        else
        {
            build_tree(1,n,1);
            //check(1,n,1);
            //cout<<111<<endl;
            for(int i=1;i<=q;i++)
            {
                l[i]++;
                r[i]--;
                if(a[i]=="toggle")
                {
                    update(1,n,l[i],1,i);
                    //check(1,n,1);
                }
                else
                {
                    cout<<query(1,n,l[i],r[i],1,i)<<endl;
                }
            }
        }
    }
}
int main()
{
    speed();
    read();
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12380 KB Output is correct
2 Correct 3 ms 12380 KB Output is correct
3 Correct 3 ms 12380 KB Output is correct
4 Correct 3 ms 12380 KB Output is correct
5 Correct 3 ms 12380 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 3 ms 12392 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 15424 KB Output is correct
2 Correct 57 ms 15444 KB Output is correct
3 Correct 63 ms 15440 KB Output is correct
4 Correct 71 ms 21956 KB Output is correct
5 Correct 77 ms 22152 KB Output is correct
6 Correct 63 ms 21948 KB Output is correct
7 Correct 97 ms 13540 KB Output is correct
8 Correct 81 ms 18884 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Incorrect 5 ms 16476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12380 KB Output is correct
2 Correct 3 ms 12380 KB Output is correct
3 Correct 3 ms 12380 KB Output is correct
4 Correct 3 ms 12380 KB Output is correct
5 Correct 3 ms 12380 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 3 ms 12392 KB Output is correct
8 Correct 60 ms 15424 KB Output is correct
9 Correct 57 ms 15444 KB Output is correct
10 Correct 63 ms 15440 KB Output is correct
11 Correct 71 ms 21956 KB Output is correct
12 Correct 77 ms 22152 KB Output is correct
13 Correct 63 ms 21948 KB Output is correct
14 Correct 97 ms 13540 KB Output is correct
15 Correct 81 ms 18884 KB Output is correct
16 Correct 4 ms 14428 KB Output is correct
17 Incorrect 5 ms 16476 KB Output isn't correct
18 Halted 0 ms 0 KB -