Submission #603883

#	Time	Username	Problem	Language	Result	Execution time	Memory
603883		OttoTheDino	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2701 ms	114756 KiB

street_lamps

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

#define rep(i,s,e)                  for (int i = s; i <= e; ++i)
#define pb                          push_back
#define fi                          first
#define se                          second
#define len(a)                      (int)a.size()
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

const int mx = 3e5;
int ans[mx+1], ft[mx+1];
vector<vi> g;

void upd (int x, int id) {
    for (;id<=mx;id+=id&(-id)) ft[id] += x;
}
int qry (int id) {
    int res = 0;
    for (;id;id-=id&(-id)) res += ft[id];
    return res;
}

void cdq (int l, int r) {
    if (l==r) return;
    int mid = (l+r)/2;
    cdq (l, mid);
    cdq (mid+1, r);
    vii undo;
    vector<vi> nxt;
    int a = l, b = mid+1, k = l;
    while (k<=r) {
        if (a>mid || (b<=r && g[b]<g[a])) nxt.pb(g[b++]);
        else nxt.pb(g[a++]);
        ++k;
    }
    rep (i,l,r) g[i] = nxt[i-l];
    rep (i,l,r) {
        int y = g[i][1], id = g[i][2], delt = g[i][3], t = g[i][4];
        if (t>mid) ans[id] += qry(y);
        else {
            upd(delt,y);
            undo.pb({delt,y});
        }
    }
    for (ii el : undo) upd(-el.fi, el.se);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q; cin >> n >> q;
    bool b[n+1]; 
    string s; cin >> s;
    set<int> st;
    st.insert(0);
    st.insert(n+1);
    rep (i,1,n) {
        b[i] = s[i-1]-'0';
        if (!b[i]) st.insert(i);
    }
    vi get;
    rep (i,1,q) {
        string tp; cin >> tp;
        int t = len(g);
        if (tp[0]=='t') {
            int u; cin >> u;
            int prv = *--st.lower_bound(u)+1, nxt = *st.upper_bound(u)-1, c = 2*b[u]-1;
            g.pb({prv,mx+1-nxt,0,c*i,t++}); 
            if (u+1<=mx) g.pb({u+1,mx+1-nxt,0,-c*i,t++});
            if (u-1>0) g.pb({prv,mx+1-(u-1),0,-c*i,t++});
            if (b[u]) st.insert(u);
            else st.erase(u);
            b[u] ^= 1;
        }
        else {
            int x, y; cin >> x >> y;
            --y;
            get.pb(i);
            if (*st.lower_bound(x)>y) ans[i] += i;
            g.pb({x,mx+1-y,i,0,t++});
        }
    }
    cdq(0,len(g)-1);
    for (int el : get) cout << ans[el] << "\n";

    return 0;
}

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