Submission #1163067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163067		Otalp	Street Lamps (APIO19_street_lamps)	C++20	0 / 100	2 ms	5260 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define unm unordered_map

const ll mod = 1e9 + 7;
const int MAXN = 2e5 + 5;
const int MAXA = 2e5 + 5;


vector<pii> d[200100];
int a[200100];
pii b[200100];


void upd(int l, int r, int x, int h){
    for(int i=l; i<=r; i++){
        d[i].pb({b[i].ff, h-b[i].ss});
        b[i] = {x, h};
    }
}

int get(int pos, int x, int h){
    int res = 0;
    if(b[pos].ff <= x) res += h-b[pos].ss + 1;
    for(pii g: d[pos]){
        if(g.ff <= x) res += g.ss;
    }
    return res;
}

void solve(){
    int n, m;
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        char c;
        cin>>c;
        a[i] = c -'0';
    }
    set<pii> q;
    for(int i=1; i<=n;){
        int h = 0;
        while(i + h <= n and a[i + h] == a[i]) h++;
        if(a[i] == 1){
            q.insert({i, i + h - 1}); 
            int k = i;
            while(h) b[i] = {k, 0}, h--, i++; 
        }
        else{
            // upd(i, i + h - 1, n + 1, 0); 
            int k = i;
            while(h) b[i] = {n + 1, 0}, h--, i++;
        }
    }
    for(int i=1; i<=m; i++){
        string c;
        cin>>c;
        if(c[0] == 'q'){
            int l, r;
            cin>>l>>r;
            cout<<get(r-1, l, i-1)<<'\n'; 
        }
        else{
            int x;
            cin>>x;
            if(a[x] == 0){
                a[x] = 1;
                int l=x, r=x;
                if(x > 1 and a[x - 1]){
                    auto g = q.upper_bound({x, 1e9});
                    g--;
                    l = g -> ff;
                    q.erase(g);
                }
                if(x < n and a[x + 1]){
                    auto g = q.upper_bound({x, 1e9});
                    g--;
                    r = g -> ss;
                    q.erase(g);
                }
                q.insert({l, r});
                upd(x, r, l, i);
            }  
            else{
                a[x] = 0;
                auto g = q.upper_bound({x, 1e9});
                g--;
                int l = g -> ff, r = g -> ss;
                q.erase(g);
                upd(x, x, n + 1, i);
                if(l <= x-1){
                    q.insert({l, x-1});
                }
                if(x + 1 <= r){
                    q.insert({x + 1, r});
                    upd(x + 1, r, x + 1, i);
                }
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
        cout<<'\n';
    }
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20