oj.uz

Submission #1089084

# Submission time Handle Problem Language Result Execution time Memory
1089084 2024-09-15T23:56:13 Z DylanSmith Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2985 ms 302804 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 53848 KB Output is correct
2 Correct 559 ms 60548 KB Output is correct
3 Correct 786 ms 77648 KB Output is correct
4 Correct 2049 ms 224896 KB Output is correct
5 Correct 1913 ms 226992 KB Output is correct
6 Correct 2250 ms 244152 KB Output is correct
7 Correct 237 ms 71752 KB Output is correct
8 Correct 1869 ms 302652 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 3 ms 1100 KB Output is correct
5 Correct 2288 ms 226452 KB Output is correct
6 Correct 2334 ms 226316 KB Output is correct
7 Correct 1851 ms 226704 KB Output is correct
8 Correct 1930 ms 302804 KB Output is correct
9 Correct 70 ms 17396 KB Output is correct
10 Correct 75 ms 23916 KB Output is correct
11 Correct 73 ms 24064 KB Output is correct
12 Correct 261 ms 72284 KB Output is correct
13 Correct 2001 ms 302716 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 3 ms 860 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 4 ms 856 KB Output is correct
5 Correct 937 ms 149424 KB Output is correct
6 Correct 1579 ms 191224 KB Output is correct
7 Correct 2181 ms 243884 KB Output is correct
8 Correct 2985 ms 297908 KB Output is correct
9 Correct 733 ms 82236 KB Output is correct
10 Correct 601 ms 84772 KB Output is correct
11 Correct 725 ms 82756 KB Output is correct
12 Correct 618 ms 84488 KB Output is correct
13 Correct 722 ms 82500 KB Output is correct
14 Correct 632 ms 84952 KB Output is correct
15 Correct 239 ms 71896 KB Output is correct
16 Correct 1937 ms 302772 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 383 ms 53848 KB Output is correct
9 Correct 559 ms 60548 KB Output is correct
10 Correct 786 ms 77648 KB Output is correct
11 Correct 2049 ms 224896 KB Output is correct
12 Correct 1913 ms 226992 KB Output is correct
13 Correct 2250 ms 244152 KB Output is correct
14 Correct 237 ms 71752 KB Output is correct
15 Correct 1869 ms 302652 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 2 ms 860 KB Output is correct
18 Correct 3 ms 860 KB Output is correct
19 Correct 3 ms 1100 KB Output is correct
20 Correct 2288 ms 226452 KB Output is correct
21 Correct 2334 ms 226316 KB Output is correct
22 Correct 1851 ms 226704 KB Output is correct
23 Correct 1930 ms 302804 KB Output is correct
24 Correct 70 ms 17396 KB Output is correct
25 Correct 75 ms 23916 KB Output is correct
26 Correct 73 ms 24064 KB Output is correct
27 Correct 261 ms 72284 KB Output is correct
28 Correct 2001 ms 302716 KB Output is correct
29 Correct 2 ms 600 KB Output is correct
30 Correct 3 ms 860 KB Output is correct
31 Correct 3 ms 860 KB Output is correct
32 Correct 4 ms 856 KB Output is correct
33 Correct 937 ms 149424 KB Output is correct
34 Correct 1579 ms 191224 KB Output is correct
35 Correct 2181 ms 243884 KB Output is correct
36 Correct 2985 ms 297908 KB Output is correct
37 Correct 733 ms 82236 KB Output is correct
38 Correct 601 ms 84772 KB Output is correct
39 Correct 725 ms 82756 KB Output is correct
40 Correct 618 ms 84488 KB Output is correct
41 Correct 722 ms 82500 KB Output is correct
42 Correct 632 ms 84952 KB Output is correct
43 Correct 239 ms 71896 KB Output is correct
44 Correct 1937 ms 302772 KB Output is correct
45 Correct 115 ms 28692 KB Output is correct
46 Correct 224 ms 35128 KB Output is correct
47 Correct 920 ms 100264 KB Output is correct
48 Correct 2033 ms 224160 KB Output is correct
49 Correct 81 ms 24004 KB Output is correct
50 Correct 74 ms 24060 KB Output is correct
51 Correct 77 ms 24076 KB Output is correct
52 Correct 84 ms 24692 KB Output is correct
53 Correct 75 ms 24568 KB Output is correct
54 Correct 76 ms 24568 KB Output is correct