oj.uz

Submission #971924

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 15424 KB Output is correct
2 Correct 58 ms 15440 KB Output is correct
3 Correct 62 ms 15384 KB Output is correct
4 Correct 70 ms 21952 KB Output is correct
5 Correct 71 ms 21988 KB Output is correct
6 Correct 63 ms 21960 KB Output is correct
7 Correct 83 ms 13484 KB Output is correct
8 Correct 89 ms 19208 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 12380 KB Output isn't correct
2 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 12376 KB Output is correct
2 Correct 3 ms 12380 KB Output is correct
3 Correct 3 ms 12376 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 3 ms 12380 KB Output is correct
6 Correct 3 ms 12376 KB Output is correct
7 Correct 3 ms 12376 KB Output is correct
8 Correct 66 ms 15424 KB Output is correct
9 Correct 58 ms 15440 KB Output is correct
10 Correct 62 ms 15384 KB Output is correct
11 Correct 70 ms 21952 KB Output is correct
12 Correct 71 ms 21988 KB Output is correct
13 Correct 63 ms 21960 KB Output is correct
14 Correct 83 ms 13484 KB Output is correct
15 Correct 89 ms 19208 KB Output is correct
16 Incorrect 3 ms 12380 KB Output isn't correct
17 Halted 0 ms 0 KB -