Submission #1156243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156243		Sharky	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	2331 ms	236020 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define int long long
#define fi first
#define se second

#define L(i, j, k) for (int i = (j); i <= (k); i++)
#define R(i, j, k) for (int i = (j); i >= (k); i--)
#define all(x) x.begin(), x.end()

// range add, point sum
// <=> point add, range sum

const int N = 3e5 + 5;
int n, Q;
string s;
int stat[N], ans[N];
vector<pair<int, int>> vec;
set<pair<int, int>> st;

struct Query {
    int ty, x, y, f, ti, id;
} q[N * 12], tq[N * 12];

int qcnt = 0, ask = 0;

void add(int time, int x, int y) { // [x, y], [x, y] += time
    ++qcnt; q[qcnt] = (Query) {1, y, y, time, qcnt, 0};
    ++qcnt; q[qcnt] = (Query) {1, x-1, y, -time, qcnt, 0};
    ++qcnt; q[qcnt] = (Query) {1, y, x-1, -time, qcnt, 0};
    ++qcnt; q[qcnt] = (Query) {1, x-1, x-1, time, qcnt, 0};
}

int fen[N], z;

void upd(int i, int k) {
    if (!i) {
        z += k;
        return;
    }
    for (; i < N; i += (i & -i)) fen[i] += k;
}

int query(int i) {
    if (i < 0) return 0;
    int res = z;
    for (; i; i -= (i & -i)) res += fen[i];
    return res;
}

void dnc(int l, int r) {
    if (l == r) return;
    int mid = (l + r) / 2;
    for (int i = l; i <= r; i++) {
        if (q[i].ty == 1 && q[i].ti <= mid) upd(q[i].y, q[i].f);
        else if (q[i].ty == 2 && q[i].ti > mid) ans[q[i].id] += query(q[i].y) * q[i].f;
    }
    int p1 = l-1, p2 = mid;
    for (int i = l; i <= r; i++) {
        if (q[i].ty == 1 && q[i].ti <= mid) upd(q[i].y, -q[i].f);
        if (q[i].ti <= mid) tq[++p1] = q[i];
        else tq[++p2] = q[i];
    }
    for (int i = l; i <= r; i++) q[i] = tq[i];
    dnc(l, mid);
    dnc(mid + 1, r);
}

void solve() {
    cin >> n >> Q >> s;
    s = "?" + s;
    for (int i = 1; i <= n; i++) {
        stat[i] = (s[i] - '0');
        if (s[i] == '0') continue;
        if (!vec.empty() && vec.back().se + 1 == i) vec.back().se++;
        else vec.push_back({i, i});
    }
    for (auto& [xx, yy] : vec) st.insert({xx, yy});
    for (int i = 1; i <= Q; i++) {
        string op;
        cin >> op;
        if (op == "toggle") {
            int x;
            cin >> x;
            if (!stat[x]) {
                int rl = x, rr = x;
                auto it = st.lower_bound({x, x});
                // cout << "ex\n";
                if (it != st.begin()) {
                    // cout << i << " " << "enter\n";
                    --it;
                    if (it->second == x - 1) {
                        rl = it->first;
                        add(i, it->first, it->second);
                        it = st.erase(it);
                    } else ++it;
                }
                // cout << "ex\n";
                if (it != st.end() && it->first == x + 1) {
                    // cout << i << "enter\n";
                    rr = it->second;
                    add(i, it->first, it->second);
                    st.erase(it);
                }
                // cout << "ex\n";
                add(-i, rl, rr);
                st.insert({rl, rr});
            } else {
                auto it = --st.lower_bound({x, 1e9});
                if (it->first == it->second) {
                    add(i, x, x);
                    st.erase(it);
                } else if (it->first == x) {
                    int r = it->second;
                    add(i, it->first, it->second);
                    st.erase(it);
                    add(-i, x+1, r);
                    st.insert({x+1, r});
                } else if (it->second == x) {
                    int l = it->first;
                    add(i, it->first, it->second);
                    st.erase(it);
                    add(-i, l, x-1);
                    st.insert({l, x-1});
                } else {
                    int l = it->first, r = it->second;
                    add(i, it->first, it->second);
                    st.erase(it);
                    add(-i, l, x-1);
                    st.insert({l, x-1});
                    add(-i, x+1, r);
                    st.insert({x+1, r});
                }
            }
            stat[x] ^= 1;
        } else if (op == "query") {
            int a, b;
            cin >> a >> b;
            b--, ++ask;
            auto it = st.lower_bound({a, 1e9});
            if (it != st.begin()) {
                --it;
                if (it->second >= b) ans[ask] += i;
            }
            ++qcnt; q[qcnt] = (Query) {2, n, n, 1, qcnt, ask};
            ++qcnt; q[qcnt] = (Query) {2, a - 1, n, -1, qcnt, ask};
            ++qcnt; q[qcnt] = (Query) {2, n, b - 1, -1, qcnt, ask};
            ++qcnt; q[qcnt] = (Query) {2, a - 1, b - 1, 1, qcnt, ask};
        }
        // for (auto [ll, rr] : st) cout << i << " " << ll << " " << rr << '\n';
    }
    sort(q + 1, q + qcnt + 1, [] (auto lhs, auto rhs) {
        if (lhs.x == rhs.x) {
            if (lhs.y == rhs.y) return lhs.ty < rhs.ty;
            return lhs.y < rhs.y;
        }
        return lhs.x < rhs.x;
    });
    dnc(1, qcnt);
    for (int i = 1; i <= ask; i++) cout << ans[i] << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int test = 1;
    // cin >> test;
    while (test--) solve();
}

/*
5 9
01001
query 1 6
toggle 3
toggle 3
toggle 2
toggle 3
toggle 2
toggle 4
query 2 6
query 2 3
*/

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