oj.uz

Submission #926305

# Submission time Handle Problem Language Result Execution time Memory
926305 2024-02-12T19:01:43 Z TAhmed33 Street Lamps (APIO19_street_lamps) C++
100 / 100
 4906 ms 383828 KB 
#include <bits/stdc++.h>
using namespace std;
struct Implicit {
    vector <int> tree, tl, tr; int cnt;
    int create () {
        ++cnt; tl.push_back(-1); tr.push_back(-1); tree.push_back(0); return cnt;
    }
    void init () {
        tree.push_back(0); tl.push_back(-1); tr.push_back(-1); cnt = 0;
    }
    void update (int l, int r, int a, int b, int node) {
        if (l == r) {
            tree[node] += b; return;
        }
        int mid = (l + r) >> 1;
        if (a <= mid) {
            if (tl[node] == -1) {
                int z = create(); tl[node] = z;
            } else tree[node] -= tree[tl[node]];
            assert(tl[node] != -1);
            update(l, mid, a, b, tl[node]);
            tree[node] += tree[tl[node]];
        } else {
            if (tr[node] == -1) {
                int z = create(); tr[node] = z; 
            }
            else tree[node] -= tree[tr[node]];
            assert(tr[node] != -1);
            update(mid + 1, r, a, b, tr[node]);
            tree[node] += tree[tr[node]];
        }
    }
    int get (int l, int r, int a, int b, int node) {
        if (l > b || r < a) return 0;
        if (l >= a && r <= b) return tree[node];
        int sum = 0, mid = (l + r) >> 1;
        if (tl[node] != -1) sum += get(l, mid, a, b, tl[node]);
        if (tr[node] != -1) sum += get(mid + 1, r, a, b, tr[node]);
        return sum;
    }
};
typedef long long ll;
const int MAXN = 3e5 + 25;
bool a[MAXN];
int n, q;
set <vector <int>> cur;
Implicit tree[MAXN << 1];
void init () {
    for (int i = 1; i <= n; i++) {
        if (!a[i]) continue;
        int j = i; while (j + 1 <= n && a[j + 1]) j++;
        cur.insert({i, j, 0});
        i = j;
    }
}   
void update (int l, int r, int a, int b, int c, int node) {
    if (l > a || r < a) return;
    tree[node].update(1, n, b, c, 0);
    //cout << l << " " << r << " " << a << " " << b << " " << c << " " << node << '\n';
    if (l == r) return;
    int mid = (l + r) >> 1, tl = node + 1, tr = node + 2 * (mid - l + 1);
    update(l, mid, a, b, c, tl); update(mid + 1, r, a, b, c, tr);
}
int dfs (int l, int r, int a, int b, int c, int node) {
    if (l > b || r < a) return 0;
    //cout << l << " " << r << " " << a << " " << b << " " << c << " " << node << '\n';
    if (l >= a && r <= b) return tree[node].get(1, n, c, n, 0);
    int mid = (l + r) >> 1, tl = node + 1, tr = node + 2 * (mid - l + 1);
    return dfs(l, mid, a, b, c, tl) + dfs(mid + 1, r, a, b, c, tr);
}
void add (vector <int> x, int y) {
    cur.erase(x);
    update(1, n, x[0], x[1], y - x[2], 1);
}
void insert (vector <int> x) {
    cur.insert(x);
}
int query (int l, int r, int x) { 
    int sum = dfs(1, n, 1, l, r, 1);
    auto z = cur.upper_bound({l, n + 1, 0});
    if (z != cur.begin()) {
        z--; auto g = *z; 
        if (g[0] <= l && r <= g[1]) sum += x - g[2];
    }
    return sum;
}
int main () {
    cin >> n >> q;
    for (int i = 1; i < 2 * n; i++) tree[i].init();
    for (int i = 1; i <= n; i++) {
        char x; cin >> x; a[i] = x == '1';
    }
    init();
    for (int t = 1; t <= q; t++) {
        string x; cin >> x;
        if (x == "query") {
            int l, r; cin >> l >> r; r--;
            cout << query(l, r, t) << '\n';
        } else {
            int x; cin >> x; a[x] ^= 1;
            if (!a[x]) {
                auto z = *(--cur.lower_bound({x + 1, 0, 0}));
                add(z, t); 
                auto l = z; l[2] = t; l[1] = x - 1;
                if (l[0] <= l[1]) insert(l);
                l = z; l[2] = t; l[0] = x + 1;
                if (l[0] <= l[1]) insert(l);
            } else {
                int mn = x, mx = x;
                if (x < n && a[x + 1]) {
                    auto z = *(cur.lower_bound({x + 1, x + 1, 0}));
                    add(z, t);
                    mx = z[1];
                }
                if (x > 1 && a[x - 1]) {
                    auto z = *(--cur.lower_bound({x, x, 0}));
                    add(z, t);
                    mn = z[0];
                }
                vector <int> z = {mn, mx, t};
                insert(z);
            }
        }   
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 47192 KB Output is correct
2 Correct 10 ms 47192 KB Output is correct
3 Correct 10 ms 47196 KB Output is correct
4 Correct 10 ms 47320 KB Output is correct
5 Correct 10 ms 47448 KB Output is correct
6 Correct 11 ms 47192 KB Output is correct
7 Correct 10 ms 47196 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 48692 KB Output is correct
2 Correct 537 ms 48556 KB Output is correct
3 Correct 866 ms 59248 KB Output is correct
4 Correct 3498 ms 309576 KB Output is correct
5 Correct 3614 ms 332232 KB Output is correct
6 Correct 3560 ms 322300 KB Output is correct
7 Correct 777 ms 110416 KB Output is correct
8 Correct 788 ms 111780 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 47964 KB Output is correct
2 Correct 14 ms 47964 KB Output is correct
3 Correct 14 ms 47960 KB Output is correct
4 Correct 12 ms 47452 KB Output is correct
5 Correct 4785 ms 383828 KB Output is correct
6 Correct 4520 ms 374532 KB Output is correct
7 Correct 3542 ms 330920 KB Output is correct
8 Correct 809 ms 111800 KB Output is correct
9 Correct 446 ms 50996 KB Output is correct
10 Correct 482 ms 51328 KB Output is correct
11 Correct 496 ms 51652 KB Output is correct
12 Correct 824 ms 110648 KB Output is correct
13 Correct 812 ms 111820 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 47452 KB Output is correct
2 Correct 13 ms 47708 KB Output is correct
3 Correct 13 ms 47752 KB Output is correct
4 Correct 13 ms 47964 KB Output is correct
5 Correct 1035 ms 126704 KB Output is correct
6 Correct 2225 ms 259820 KB Output is correct
7 Correct 3352 ms 321928 KB Output is correct
8 Correct 4906 ms 359228 KB Output is correct
9 Correct 492 ms 51320 KB Output is correct
10 Correct 378 ms 50340 KB Output is correct
11 Correct 473 ms 51540 KB Output is correct
12 Correct 335 ms 50260 KB Output is correct
13 Correct 502 ms 51536 KB Output is correct
14 Correct 324 ms 50352 KB Output is correct
15 Correct 812 ms 110516 KB Output is correct
16 Correct 830 ms 111904 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 47192 KB Output is correct
2 Correct 10 ms 47192 KB Output is correct
3 Correct 10 ms 47196 KB Output is correct
4 Correct 10 ms 47320 KB Output is correct
5 Correct 10 ms 47448 KB Output is correct
6 Correct 11 ms 47192 KB Output is correct
7 Correct 10 ms 47196 KB Output is correct
8 Correct 473 ms 48692 KB Output is correct
9 Correct 537 ms 48556 KB Output is correct
10 Correct 866 ms 59248 KB Output is correct
11 Correct 3498 ms 309576 KB Output is correct
12 Correct 3614 ms 332232 KB Output is correct
13 Correct 3560 ms 322300 KB Output is correct
14 Correct 777 ms 110416 KB Output is correct
15 Correct 788 ms 111780 KB Output is correct
16 Correct 13 ms 47964 KB Output is correct
17 Correct 14 ms 47964 KB Output is correct
18 Correct 14 ms 47960 KB Output is correct
19 Correct 12 ms 47452 KB Output is correct
20 Correct 4785 ms 383828 KB Output is correct
21 Correct 4520 ms 374532 KB Output is correct
22 Correct 3542 ms 330920 KB Output is correct
23 Correct 809 ms 111800 KB Output is correct
24 Correct 446 ms 50996 KB Output is correct
25 Correct 482 ms 51328 KB Output is correct
26 Correct 496 ms 51652 KB Output is correct
27 Correct 824 ms 110648 KB Output is correct
28 Correct 812 ms 111820 KB Output is correct
29 Correct 13 ms 47452 KB Output is correct
30 Correct 13 ms 47708 KB Output is correct
31 Correct 13 ms 47752 KB Output is correct
32 Correct 13 ms 47964 KB Output is correct
33 Correct 1035 ms 126704 KB Output is correct
34 Correct 2225 ms 259820 KB Output is correct
35 Correct 3352 ms 321928 KB Output is correct
36 Correct 4906 ms 359228 KB Output is correct
37 Correct 492 ms 51320 KB Output is correct
38 Correct 378 ms 50340 KB Output is correct
39 Correct 473 ms 51540 KB Output is correct
40 Correct 335 ms 50260 KB Output is correct
41 Correct 502 ms 51536 KB Output is correct
42 Correct 324 ms 50352 KB Output is correct
43 Correct 812 ms 110516 KB Output is correct
44 Correct 830 ms 111904 KB Output is correct
45 Correct 267 ms 49812 KB Output is correct
46 Correct 363 ms 49932 KB Output is correct
47 Correct 1616 ms 155736 KB Output is correct
48 Correct 3164 ms 309508 KB Output is correct
49 Correct 573 ms 51324 KB Output is correct
50 Correct 599 ms 51304 KB Output is correct
51 Correct 565 ms 51560 KB Output is correct
52 Correct 577 ms 51992 KB Output is correct
53 Correct 564 ms 52040 KB Output is correct
54 Correct 588 ms 52236 KB Output is correct