Submission #1163071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163071		Otalp	Street Lamps (APIO19_street_lamps)	C++20	0 / 100	4 ms	7496 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[300100];
int a[300100];
pii b[300100];


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(q.size() and x > 1 and a[x - 1]){
    //                 auto g = q.upper_bound({x, 1e9});
    //                 g--;
    //                 l = g -> ff;
    //                 q.erase(g);
    //             }
    //             if(q.size() and 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