oj.uz

Submission #971881

# Submission time Handle Problem Language Result Execution time Memory
971881 2024-04-29T12:42:12 Z vivkostov Street Lamps (APIO19_street_lamps) C++14
40 / 100
 82 ms 21988 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++)
            {
                if(a[i]=="toggle")
                {
                    update(1,n,l[i]+1,1,i);
                    //check(1,n,1);
                }
                else
                {
                    cout<<query(1,n,l[i]+1,r[i]-1,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 12376 KB Output is correct
2 Correct 4 ms 12380 KB Output is correct
3 Correct 3 ms 12380 KB Output is correct
4 Correct 5 ms 12380 KB Output is correct
5 Correct 5 ms 12380 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 3 ms 12480 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 15436 KB Output is correct
2 Correct 58 ms 15444 KB Output is correct
3 Correct 62 ms 15384 KB Output is correct
4 Correct 73 ms 21928 KB Output is correct
5 Correct 76 ms 21988 KB Output is correct
6 Correct 64 ms 21956 KB Output is correct
7 Correct 77 ms 13504 KB Output is correct
8 Correct 82 ms 18952 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14424 KB Output is correct
2 Incorrect 4 ms 16616 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 12376 KB Output is correct
2 Correct 4 ms 12380 KB Output is correct
3 Correct 3 ms 12380 KB Output is correct
4 Correct 5 ms 12380 KB Output is correct
5 Correct 5 ms 12380 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 3 ms 12480 KB Output is correct
8 Correct 57 ms 15436 KB Output is correct
9 Correct 58 ms 15444 KB Output is correct
10 Correct 62 ms 15384 KB Output is correct
11 Correct 73 ms 21928 KB Output is correct
12 Correct 76 ms 21988 KB Output is correct
13 Correct 64 ms 21956 KB Output is correct
14 Correct 77 ms 13504 KB Output is correct
15 Correct 82 ms 18952 KB Output is correct
16 Correct 4 ms 14424 KB Output is correct
17 Incorrect 4 ms 16616 KB Output isn't correct
18 Halted 0 ms 0 KB -