Submission #1260457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260457		lastgirl	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	1721 ms	114940 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;

// Cập nhật giá trị x tại vị trí id
// Tăng giá trị của các nút chứa id
void upd(int x, int id) {
    for (; id > 0; id -= id & (-id)) ft[id] += x;
}

// Truy vấn tổng hậu tố từ id đến mx
// Tổng giá trị của các nút chứa id và các nút sau đó
int qry(int id) {
    int res = 0;
    for (; id <= mx; 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][0] < g[a][0])) 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, nxt, 0, c * i, t++});
            if (u + 1 <= mx) g.pb({u + 1, nxt, 0, -c * i, t++});
            if (u - 1 > 0) g.pb({prv, 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, 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