oj.uz

Submission #971927

# Submission time Handle Problem Language Result Execution time Memory
971927 2024-04-29T13:58:49 Z vivkostov Street Lamps (APIO19_street_lamps) C++14
60 / 100
 218 ms 30220 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
        {
            for(int i=1;i<n;i++)
            {
                state[i]=0;
            }
            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 4 ms 12380 KB Output is correct
2 Correct 3 ms 12476 KB Output is correct
3 Correct 4 ms 12380 KB Output is correct
4 Correct 3 ms 12380 KB Output is correct
5 Correct 3 ms 12632 KB Output is correct
6 Correct 3 ms 12376 KB Output is correct
7 Correct 3 ms 12380 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 15364 KB Output is correct
2 Correct 57 ms 15372 KB Output is correct
3 Correct 59 ms 15700 KB Output is correct
4 Correct 72 ms 21948 KB Output is correct
5 Correct 73 ms 22000 KB Output is correct
6 Correct 66 ms 21988 KB Output is correct
7 Correct 74 ms 13540 KB Output is correct
8 Correct 80 ms 18920 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16476 KB Output is correct
2 Correct 4 ms 16476 KB Output is correct
3 Correct 4 ms 16476 KB Output is correct
4 Correct 3 ms 14428 KB Output is correct
5 Correct 113 ms 28972 KB Output is correct
6 Correct 144 ms 30220 KB Output is correct
7 Correct 164 ms 28248 KB Output is correct
8 Correct 207 ms 27004 KB Output is correct
9 Correct 77 ms 18172 KB Output is correct
10 Correct 81 ms 18356 KB Output is correct
11 Correct 82 ms 18744 KB Output is correct
12 Correct 218 ms 23376 KB Output is correct
13 Correct 189 ms 26848 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12380 KB Output is correct
2 Correct 3 ms 12476 KB Output is correct
3 Correct 4 ms 12380 KB Output is correct
4 Correct 3 ms 12380 KB Output is correct
5 Correct 3 ms 12632 KB Output is correct
6 Correct 3 ms 12376 KB Output is correct
7 Correct 3 ms 12380 KB Output is correct
8 Correct 55 ms 15364 KB Output is correct
9 Correct 57 ms 15372 KB Output is correct
10 Correct 59 ms 15700 KB Output is correct
11 Correct 72 ms 21948 KB Output is correct
12 Correct 73 ms 22000 KB Output is correct
13 Correct 66 ms 21988 KB Output is correct
14 Correct 74 ms 13540 KB Output is correct
15 Correct 80 ms 18920 KB Output is correct
16 Correct 4 ms 16476 KB Output is correct
17 Correct 4 ms 16476 KB Output is correct
18 Correct 4 ms 16476 KB Output is correct
19 Correct 3 ms 14428 KB Output is correct
20 Correct 113 ms 28972 KB Output is correct
21 Correct 144 ms 30220 KB Output is correct
22 Correct 164 ms 28248 KB Output is correct
23 Correct 207 ms 27004 KB Output is correct
24 Correct 77 ms 18172 KB Output is correct
25 Correct 81 ms 18356 KB Output is correct
26 Correct 82 ms 18744 KB Output is correct
27 Correct 218 ms 23376 KB Output is correct
28 Correct 189 ms 26848 KB Output is correct
29 Correct 5 ms 16472 KB Output is correct
30 Incorrect 4 ms 16684 KB Output isn't correct
31 Halted 0 ms 0 KB -