oj.uz

Submission #934196

# Submission time Handle Problem Language Result Execution time Memory
934196 2024-02-27T00:45:46 Z irmuun Street Lamps (APIO19_street_lamps) C++17
20 / 100
 54 ms 1512 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,0,n-1);
    }
    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]=min(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 1e18;
        }
        if(L <= l && r <= R){
            return d[node];
        }
        ll mid=(l+r)/2;
        return min(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]=min(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];
    }
    if(n<=100&&q<=100){
        vector<pair<ll,ll>>que(q);
        for(ll i=0;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};
                ll ans=0;
                for(ll j=1;j<=n;j++){
                    cur[j]=s[j];
                }
                for(ll j=0;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;
    }
    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++){
        string t;
        cin>>t;
        if(t=="toggle"){
            ll j;
            cin>>j;
            if(bef[j].ss==1){
                ans[j]+=i-bef[j].ss;
            }
            bef[j].ff=i;
            bef[j].ss=1-bef[j].ss;
        }
        else{
            ll a,b;
            cin>>a>>b;
            if(a==b-1){
                if(bef[a].ss==1){
                    ans[a]+=i-bef[a].ff;
                }
                bef[a].ff=i;
                cout<<ans[a]<<"\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 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Incorrect 54 ms 1512 KB Output isn't correct
9 Halted 0 ms 0 KB -