Submission #362394

#	Time	Username	Problem	Language	Result	Execution time	Memory
362394		arbor	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1414 ms	85264 KiB

street_lamps

#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
#define eb emplace_back
#define pb push_back
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
const int MN = 3e5 + 5;
int N, Q, a[MN];
set<int> dat;

int b[MN];
void upd(int i, int v) { for (; i < MN; i += i & -i) b[i] += v; }
int qry(int i) { int r = 0; for (; i; i -= i & -i) r += b[i]; return r; }

struct Query {
    int x, y, v, id;
};
vector<Query> qs;

int ans[MN];

// maintain relative ordering in terms of queries
// split left right by x value
void cdq(int l, int r, vector<Query> &v) {
    if (v.empty() || l > r) return;
    int m = (l + r) / 2;
    vector<Query> vl, vr;
    for (auto q : v) {
        if (q.x <= m) {
            if (q.id == -1) upd(q.y, q.v);
            if (q.id != -1 && l == r) ans[q.id] += qry(q.y);
            vl.push_back(q);
        } else {
            if (q.id != -1) ans[q.id] += qry(q.y);
            vr.push_back(q);
        }
    }
    for (auto q : vl) if (q.id == -1) upd(q.y, -q.v);
    if (l < r) cdq(l, m, vl), cdq(m + 1, r, vr);
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N >> Q;

    dat.insert(0), dat.insert(N + 1);
    for (int i = 1; i <= N; i++) {
        char c; cin >> c;
        a[i] = (c == '1');
        if (!a[i]) dat.insert(i);
    }

    int pos = 0;
    for (int i = 1; i <= Q; i++) {
        string op; cin >> op;
        if (op == "query") {
            int l, r; cin >> l >> r; r--;
            pos++;
            if (*dat.lower_bound(l) > r) ans[pos] += i;
            qs.push_back({l, r, -1, pos});
        } else {
            int x, u ,v, sgn; cin >> x;
            if (a[x]) {
                auto nxt = dat.lower_bound(x), pre = nxt;
                pre--;
                u = *pre, v = *nxt;
                dat.insert(x);
                a[x] = 0;
                sgn = 1;
            } else {
                auto it = dat.find(x), pre = it, nxt = it;
                pre--, nxt++;
                u = *pre, v = *nxt;
                dat.erase(x);
                a[x] = 1;
                sgn = -1;
            }
            // [u+1,x] * [x,v-1]
            qs.push_back({u + 1, x, sgn * i, -1});
            qs.push_back({u + 1, v, -sgn * i, -1});
            qs.push_back({x + 1, x, -sgn * i, -1});
            qs.push_back({x + 1, v, sgn * i, -1});
        }
    }

    cdq(1, N, qs);

    for (int i = 1; i <= pos; i++) cout << ans[i] << '\n';
    return 0;
}

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