Submission #1089084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089084		DylanSmith	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2985 ms	302804 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)
#define lb(x,y) lower_bound(all(x),y)-begin(x)

mt19937 rng;

struct HalfCompressedBIT2D {
    int N;
    bool built = 0;
    vector<pair<int, int>> updates;
    HalfCompressedBIT2D(int N = 0) : N(N) {}
    void addUpdate(int r, int c) {
        updates.pb({r, c});
    }
    vector<vector<int>> compress;
    vector<vector<ll>> tree;
    static bool cmp(pair<int, int> &a, pair<int, int> &b) {
        return a.second < b.second;
    }
    void build() {
        sort(all(updates), cmp);
        compress = vector<vector<int>>(N, {0});
        for (auto &p : updates)
            for (int rr = p.first; rr < sz(compress); rr += rr & -rr)
                compress[rr].pb(p.second);
        tree = vector<vector<ll>>(sz(compress));
        for (int i = 0; i < sz(compress); i++) {
            tree[i] = vector<ll>(sz(compress[i]), 0);
        }
        built = 1;
    }
    void update(int r, int c, int k) {
        if (!built) build();
        for (int rr = r; rr < sz(compress); rr += rr & -rr)
            for (int cc = lb(compress[rr], c); cc < sz(compress[rr]); cc += cc & -cc)
                tree[rr][cc] += k;
    }
    ll query(int r, int c) {
        if (!built) build();
        ll res = 0;
        for (int rr = r; rr; rr -= rr & -rr)
            for (int cc = lb(compress[rr], c + 1) - 1; cc; cc -= cc & -cc)
                res += tree[rr][cc];
        return res;
    }
};

vector<bool> a;
HalfCompressedBIT2D sum;
set<int> off;
vector<int> sum2;

void addToggle(int i) {
    if (a[i - 1]) {
        int l = *prev(off.lower_bound(i)) + 1, r = *off.lower_bound(i) - 1;
        a[i - 1] = 0;
        off.insert(i);
        sum.addUpdate(l, i);
        sum.addUpdate(i + 1, i);
        sum.addUpdate(l, r + 1);
        sum.addUpdate(i + 1, r + 1);
    } else {
        off.erase(i);
        a[i - 1] = 1;
        int l = *prev(off.lower_bound(i)) + 1, r = *off.lower_bound(i) - 1;
        sum.addUpdate(l, i);
        sum.addUpdate(i + 1, i);
        sum.addUpdate(l, r + 1);
        sum.addUpdate(i + 1, r + 1);
    }
}

void toggle(int i, int t) {
    if (a[i - 1]) {
        int l = *prev(off.lower_bound(i)) + 1, r = *off.lower_bound(i) - 1;
        a[i - 1] = 0;
        off.insert(i);
        sum.update(l, i, t);
        sum.update(i + 1, i, -t);
        sum.update(l, r + 1, -t);
        sum.update(i + 1, r + 1, t);
        for (int j = i; j < sz(sum2); j += j & -j) sum2[j]--;
    } else {
        off.erase(i);
        a[i - 1] = 1;
        int l = *prev(off.lower_bound(i)) + 1, r = *off.lower_bound(i) - 1;
        sum.update(l, i, -t);
        sum.update(i + 1, i, t);
        sum.update(l, r + 1, t);
        sum.update(i + 1, r + 1, -t);
        for (int j = i; j < sz(sum2); j += j & -j) sum2[j]++;
    }
}

ll query(int l, int r, int t) {
    ll n = 0;
    for (int i = r; i; i -= i & -i) n += sum2[i];
    for (int i = l - 1; i; i -= i & -i) n -= sum2[i];
    return sum.query(l, r) + (n == r - l + 1 ? t : 0);
}

void solve() {
    int N, Q; cin >> N >> Q;
    string s; cin >> s;
    a = vector<bool>(N, 0);
    sum = HalfCompressedBIT2D(N + 1);
    for (int i = 0; i <= N + 1; i++) off.insert(i);
    sum2 = vector<int>(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        if (s[i - 1] == '1') addToggle(i);
    }
    vector<vector<int>> queries;
    for (int q = 0; q < Q; q++) {
        string type; cin >> type;
        if (type == "toggle") {
            int i; cin >> i;
            addToggle(i);
            queries.pb({0, i});
        } else {
            int l, r; cin >> l >> r; r--;
            queries.pb({1, l, r});
        }
    }
    off.clear();
    for (int i = 0; i <= N + 1; i++) off.insert(i);
    fill(all(a), 0);
    for (int i = 1; i <= N; i++) {
        if (s[i - 1] == '1') toggle(i, 0);
    }
    for (int q = 0; q < Q; q++) {
        if (!queries[q][0]) {
            toggle(queries[q][1], q + 1);
        } else {
            cout << query(queries[q][1], queries[q][2], q + 1) << "\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());

    solve();

    return 0;
}

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