Submission #1200372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200372		adiyer	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	1185 ms	36112 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

typedef int ll;

const int N = 3e5 + 11;

ll n, q, zap;
ll a[N], t[4 * N][4], ons[N], onc[N], offs[N], offc[N];

char chr;

set < ll > st;

vector < ll > qt;

vector < array < ll, 5 > > upds;

void add(ll i, ll x, ll tp){
    for(; i <= n; i = (i | (i + 1))) t[i][tp] += x;
}

ll get(ll r, ll tp){
    ll ret = 0;
    for(; r >= 0; r = (r & (r + 1)) - 1) ret += t[r][tp];
    return ret;
}

ll get(ll l, ll r, ll tp){
    return get(r, tp) - get(l - 1, tp);
}

void cdq(ll l, ll r){
    if(l == r) return;
    int md = (l + r) / 2;
    cdq(l, md), cdq(md + 1, r);
    sort(upds.begin() + l, upds.begin() + md + 1);
    sort(upds.begin() + md + 1, upds.begin() + r + 1);
    vector < pair < ll, ll > > on, off;
    ll i = l, j = md + 1;
    // cout << l << ' ' << md << ' ' << r << '\n';
    // for(ll i = l; i <= md; i++){
    //     for(auto it : upds[i]) cout << it << ' ';
    //     cout << '\n';
    // }
    // cout << '\n';
    while(i <= md || j <= r){
        ll id = 0, fg = 0;
        if(i > md || (j <= r && upds[j][0] < upds[i][0])) id = j, j++;
        else id = i, i++, fg = 1;
        if(fg && upds[id][3] == -1){
            add(upds[id][1], upds[id][2], 0), add(upds[id][1], 1, 1);
            off.push_back({upds[id][1], upds[id][2]});
        }
        else if(fg && upds[id][3] == 1){
            add(upds[id][1], upds[id][2], 2), add(upds[id][1], 1, 3);
            // cout << "Upd: " << upds[id][1] << ' ' << upds[id][2] << ' ' << get(upds[id][1], upds[id][1], 2) << '\n';
            on.push_back({upds[id][1], upds[id][2]});
        }
        else if(!fg && upds[id][3] == 0){
            // cout << "Zero: ";
            // for(auto it : upds[id]) cout << it << ' ';
            // cout << '\n';
            // cout << "Die: " << get(upds[id][1], n, 2) << '\n';
            ons[upds[id][4]] += get(upds[id][1], n, 2);
            onc[upds[id][4]] += get(upds[id][1], n, 3);
            offs[upds[id][4]] += get(upds[id][1], n, 0);
            offc[upds[id][4]] += get(upds[id][1], n, 1);
        }
    }
    while(!off.empty()){
        add(off.back().first, -off.back().second, 0);
        add(off.back().first, -1, 1);
        off.pop_back();
    }
    while(!on.empty()){
        add(on.back().first, -on.back().second, 2);
        add(on.back().first, -1, 3);
        on.pop_back();
    }
}

bool cmp(array < ll, 5 > i, array < ll, 5 > j){
    return i[2] < j[2];
}

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({i, j, 0, 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({*l + 1, *r - 1, t, 1});
                if(p + 1 <= *r - 1) upds.push_back({p + 1, *r - 1, t, -1});
                if(p - 1 >= *l + 1) upds.push_back({*l + 1, p - 1, t, -1});
            }
            else{
                auto r = st.upper_bound(p);
                auto l = r; l--;
                a[p] = 0, st.insert(p);
                upds.push_back({*l + 1, *r - 1, t, -1});
                if(p + 1 <= *r - 1) upds.push_back({p + 1, *r - 1, t, 1});
                if(p - 1 >= *l + 1) upds.push_back({*l + 1, p - 1, t, 1});
            }
        }
        else{
            ll l, r;
            cin >> l >> r, r--;
            upds.push_back({l, r, t, 0, zap++});
            qt.push_back(t);
        }
    }
    sort(upds.begin(), upds.end(), cmp);
    cdq(0, upds.size() - 1);
    for(ll i = 0; i < zap; i++){
        ll ans = offs[i] - ons[i];
        if(offc[i] < onc[i]) ans += qt[i];
        cout << ans << '\n';
    }
}

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

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