oj.uz

Submission #971923

# Submission time Handle Problem Language Result Execution time Memory
971923 2024-04-29T13:55:37 Z vivkostov Street Lamps (APIO19_street_lamps) C++14
40 / 100
 79 ms 22196 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 12480 KB Output is correct
3 Correct 4 ms 12376 KB Output is correct
4 Correct 4 ms 12380 KB Output is correct
5 Correct 4 ms 12380 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 4 ms 12380 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 15412 KB Output is correct
2 Correct 79 ms 15364 KB Output is correct
3 Correct 59 ms 15444 KB Output is correct
4 Correct 78 ms 21932 KB Output is correct
5 Correct 79 ms 22196 KB Output is correct
6 Correct 61 ms 21956 KB Output is correct
7 Correct 78 ms 13480 KB Output is correct
8 Correct 79 ms 18968 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12376 KB Output is correct
2 Incorrect 3 ms 14428 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 14428 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 12480 KB Output is correct
3 Correct 4 ms 12376 KB Output is correct
4 Correct 4 ms 12380 KB Output is correct
5 Correct 4 ms 12380 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 4 ms 12380 KB Output is correct
8 Correct 54 ms 15412 KB Output is correct
9 Correct 79 ms 15364 KB Output is correct
10 Correct 59 ms 15444 KB Output is correct
11 Correct 78 ms 21932 KB Output is correct
12 Correct 79 ms 22196 KB Output is correct
13 Correct 61 ms 21956 KB Output is correct
14 Correct 78 ms 13480 KB Output is correct
15 Correct 79 ms 18968 KB Output is correct
16 Correct 3 ms 12376 KB Output is correct
17 Incorrect 3 ms 14428 KB Output isn't correct
18 Halted 0 ms 0 KB -