oj.uz

Submission #934199

# Submission time Handle Problem Language Result Execution time Memory
934199 2024-02-27T01:00:28 Z irmuun Street Lamps (APIO19_street_lamps) C++17
40 / 100
 81 ms 19592 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct segtree{
    ll n;
    vector<ll>d;
    vector<ll>u;
    segtree(ll n):n(n){
        d.resize(4*n);
        build(1,1,n);
    }
    void build(ll node,ll l,ll r){
        if(l==r){
            d[node]=0;
            return;
        }
        ll mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        d[node]=max(d[node*2],d[node*2+1]);
    }
    ll query(ll node,ll l,ll r,ll L,ll R){
        if(l > R || r < L || L > R){
            return 0;
        }
        if(L <= l && r <= R){
            return d[node];
        }
        ll mid=(l+r)/2;
        return max(query(node*2,l,mid,L,R),query(node*2+1,mid+1,r,L,R));
    }
    void update(ll node,ll l,ll r,ll k,ll val){
        if(l>k || r<k)return;
        if(l==r){
            d[node]=val;
            return;
        }
        ll mid=(l+r)/2;
        update(node*2,l,mid,k,val);
        update(node*2+1,mid+1,r,k,val);
        d[node]=max(d[node*2],d[node*2+1]);
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,q;
    cin>>n>>q;
    char s[n+5],cur[n+5];
    for(ll i=1;i<=n;i++){
        cin>>s[i];
    }
    bool sub2=true;
    vector<pair<ll,ll>>que(q+1);
    for(ll i=1;i<=q;i++){
        string t;
        cin>>t;
        if(t=="toggle"){
            ll j;
            cin>>j;
            que[i]={j,-1};
        }
        else{
            ll a,b;
            cin>>a>>b;
            que[i]={a,b};
            sub2|=(a+1==b);
        }
    }
    if(n<=100&&q<=100){
        for(ll i=1;i<=q;i++){
            if(que[i].ss==-1) continue;
            ll ans=0;
            for(ll j=1;j<=n;j++){
                cur[j]=s[j];
            }
            ll a=que[i].ff,b=que[i].ss;
            for(ll j=1;j<=i;j++){
                bool ok=true;
                for(ll k=a;k<b;k++){
                    if(cur[k]=='0'){
                        ok=false;
                        break;
                    }
                }
                if(ok){
                    ans++;
                }
                if(que[j].ss==-1){
                    ll p=que[j].ff;
                    if(cur[p]=='1') cur[p]='0';
                    else cur[p]='1';
                }
            }
            cout<<ans<<"\n";
        }
        return 0;
    }
    if(sub2){
        vector<pair<ll,ll>>bef(n+1);
        for(ll i=1;i<=n;i++){
            bef[i].ff=0;
            bef[i].ss=s[i]-'0';
        }
        vector<ll>ans(n+1,0);
        for(ll i=1;i<=q;i++){
            if(que[i].ss==-1){
                ll j=que[i].ff;
                if(bef[j].ss==1){
                    ans[j]+=i-bef[j].ff;
                }
                bef[j].ff=i;
                bef[j].ss=1-bef[j].ss;
            }
            else{
                ll a,b;
                a=que[i].ff;
                b=que[i].ss;
                if(a==b-1){
                    if(bef[a].ss==1){
                        ans[a]+=i-bef[a].ff;
                    }
                    bef[a].ff=i;
                    cout<<ans[a]<<"\n";
                }
            }
        }
        return 0;
    }
    segtree sg(n);
    for(ll i=1;i<=n;i++){
        if(s[i]=='1'){
            sg.update(1,1,n,i,0);
        }
        else{
            sg.update(1,1,n,i,1e18);
        }
    }
    for(ll i=1;i<=q;i++){
        if(que[i].ss==-1){
            ll j=que[i].ff;
            sg.update(1,1,n,j,i);
        }
        else{
            ll a=que[i].ff,b=que[i].ss;
            ll x=sg.query(1,1,n,a,b-1);
            cout<<max(i-x,0ll)<<"\n";
        }
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 9228 KB Output is correct
2 Correct 63 ms 9044 KB Output is correct
3 Correct 59 ms 9408 KB Output is correct
4 Correct 70 ms 17492 KB Output is correct
5 Correct 71 ms 18000 KB Output is correct
6 Correct 68 ms 17344 KB Output is correct
7 Correct 79 ms 18072 KB Output is correct
8 Correct 81 ms 19592 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 55 ms 9228 KB Output is correct
9 Correct 63 ms 9044 KB Output is correct
10 Correct 59 ms 9408 KB Output is correct
11 Correct 70 ms 17492 KB Output is correct
12 Correct 71 ms 18000 KB Output is correct
13 Correct 68 ms 17344 KB Output is correct
14 Correct 79 ms 18072 KB Output is correct
15 Correct 81 ms 19592 KB Output is correct
16 Incorrect 1 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -