Submission #1200268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200268		adiyer	Street Lamps (APIO19_street_lamps)	C++20	0 / 100	5091 ms	3092 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

typedef int ll;

const int N = 3e5 + 11;

ll n, q;
ll a[N];

char chr;

set < ll > st;

vector < array < ll, 4 > > upds;

void solve(){
    cin >> n >> q;
    for(ll i = 1; i <= n; i++) cin >> chr, a[i] = chr - '0';
    for(ll i = 1; i <= n; i++)
        if(!a[i])
            st.insert(i);
    st.insert(0), st.insert(n + 1);
    for(ll i = 1; i <= n; i++){
        if(!a[i]) continue;
        ll j = i;
        while(j <= n && a[j + 1]) j++;
        upds.push_back({0, i, j, 1});
        i = j;
    }
    for(ll t = 1; t <= q; t++){
        string s;
        cin >> s;
        if(s == "toggle"){
            ll p;
            cin >> p;
            if(a[p] == 0){
                a[p] = 1, st.erase(p);
                auto r = st.upper_bound(p);
                auto l = r; l--;
                upds.push_back({t, *l + 1, *r - 1, 1});
            }
            else{
                auto r = st.upper_bound(p);
                auto l = r; l--;
                a[p] = 0, st.insert(p);
                upds.push_back({t, *l + 1, *r - 1, -1});
                if(p + 1 <= *r - 1) upds.push_back({t, p + 1, *r - 1, 1});
                if(p - 1 >= *l + 1) upds.push_back({t, *l + 1, p - 1, 1});
            }
        }
        else{
            ll l, r, ans = 0, c0 = 0, c1 = 0;
            cin >> l >> r, r--;
            for(auto it : upds){
                if(it[0] < t && it[1] <= l && r <= it[2]){
                    if(it[3] == 1) ans -= it[0], c1++;
                    else ans += it[0], c0++;
                    // cout << it[0] << ' ' << it[3] << ' ' << it[1] << ' ' << it[2] << '\n';
                }
            }
            if(c0 < c1) ans += t;
            cout << ans << '\n';
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tt = 1;
    // cin >> tt;
    while(tt--) solve();
}

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