oj.uz

Submission #942137

# Submission time Handle Problem Language Result Execution time Memory
942137 2024-03-10T09:47:01 Z Pannda Ants and Sugar (JOI22_sugar) C++17
100 / 100
 3058 ms 345964 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q, radius;
    cin >> q >> radius;
    vector<array<int, 3>> queries(q);
    vector<int> xs;
    for (int i = 0; i < q; i++) {
        cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
        if (queries[i][0] == 1) {
            xs.push_back(queries[i][1]);
        }
    }
    sort(xs.begin(), xs.end());
    xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
    int C = xs.size();

    if (C == 0) {
        for (int i = 0; i < q; i++) {
            cout << 0 << '\n';
        }
        return 0;
    }

    const long long INF = 1e18;

    struct Node {
        long long sugar = 0, lazy_sugar = 0;
        vector<vector<long long>> mn = { { 0, 0 }, { 0, 0 } };
        void merge(Node a, Node b) {
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    mn[i][j] = INF;
                }
            }
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    mn[i][j] = min(mn[i][j], a.mn[i][0] + b.mn[0][j]);
                    mn[i][j] = min(mn[i][j], a.mn[i][0] + b.mn[1][j]);
                    mn[i][j] = min(mn[i][j], a.mn[i][1] + b.mn[0][j]);
                    mn[i][j] = min(mn[i][j], a.mn[i][1] + b.mn[1][j] - sugar);
                    mn[i][0] = min(mn[i][0], a.mn[i][j]);
                    mn[0][j] = min(mn[0][j], b.mn[i][j]);
                }
            }
        }
    };

    vector<Node> nodes(4 * C);

    auto apply = [&](int idx, long long delta_sugar) -> void {
        nodes[idx].sugar += delta_sugar;
        nodes[idx].lazy_sugar += delta_sugar;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                nodes[idx].mn[i][j] += delta_sugar;
            }
        }
    };

    auto down = [&](int idx) -> void {
        if (nodes[idx].lazy_sugar == 0) return;
        apply(2 * idx + 1, nodes[idx].lazy_sugar);
        apply(2 * idx + 2, nodes[idx].lazy_sugar);
        nodes[idx].lazy_sugar = 0;
    };

    auto addAnt = [&](int x, int delta) -> void {
        x = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
        auto dfs = [&](auto self, int idx, int l, int r) -> void {
            if (l + 1 == r) {
                for (int i = 0; i < 2; i++) {
                    for (int j = 0; j < 2; j++) {
                        nodes[idx].mn[i][j] -= delta;
                    }
                }
            } else {
                down(idx);
                int m = (l + r) >> 1;
                if (x < m) self(self, 2 * idx + 1, l, m);
                else self(self, 2 * idx + 2, m, r);
                nodes[idx].merge(nodes[2 * idx + 1], nodes[2 * idx + 2]);
            }
        };
        dfs(dfs, 0, 0, C);
    };

    auto addSugar = [&](int ql, int qr, long long delta_sugar) -> void {
        ql = lower_bound(xs.begin(), xs.end(), ql) - xs.begin();
        qr = lower_bound(xs.begin(), xs.end(), qr) - xs.begin();
        if (ql == qr) return;
        auto dfs = [&](auto self, int idx, int l, int r) -> void {
            if (r <= ql || qr <= l) return;
            if (ql <= l && r <= qr) return apply(idx, delta_sugar);
            down(idx);
            int m = (l + r) >> 1;
            if (ql <= m - 1 && m + 1 <= qr) nodes[idx].sugar += delta_sugar;
            self(self, 2 * idx + 1, l, m);
            self(self, 2 * idx + 2, m, r);
            nodes[idx].merge(nodes[2 * idx + 1], nodes[2 * idx + 2]);
        };
        dfs(dfs, 0, 0, C);
    };

    auto query = [&]() -> long long {
        long long res = INF;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                res = min(res, nodes[0].mn[i][j]);
            }
        }
        return res;
    };

    long long total = 0;
    for (auto [type, x, c] : queries) {
        if (type == 1) {
            addAnt(x, +c);
            total += c;
        }
        if (type == 2) {
            addSugar(x - radius, x + radius + 1, +c);
        }
        cout << total + min(0LL, query()) << '\n';
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 5 ms 860 KB Output is correct
7 Correct 4 ms 860 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 5 ms 1372 KB Output is correct
11 Correct 6 ms 1528 KB Output is correct
12 Correct 7 ms 1372 KB Output is correct
13 Correct 7 ms 1372 KB Output is correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 8 ms 2396 KB Output is correct
17 Correct 8 ms 2396 KB Output is correct
18 Correct 8 ms 2396 KB Output is correct
19 Correct 5 ms 1516 KB Output is correct
20 Correct 9 ms 2396 KB Output is correct
21 Correct 8 ms 1372 KB Output is correct
22 Correct 8 ms 2396 KB Output is correct
23 Correct 9 ms 1584 KB Output is correct
24 Correct 8 ms 2396 KB Output is correct
25 Correct 7 ms 1560 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 432 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1492 ms 86064 KB Output is correct
5 Correct 734 ms 86192 KB Output is correct
6 Correct 1690 ms 100168 KB Output is correct
7 Correct 814 ms 86732 KB Output is correct
8 Correct 2120 ms 118556 KB Output is correct
9 Correct 1535 ms 179412 KB Output is correct
10 Correct 2289 ms 118476 KB Output is correct
11 Correct 1626 ms 179284 KB Output is correct
12 Correct 689 ms 78512 KB Output is correct
13 Correct 946 ms 108280 KB Output is correct
14 Correct 1554 ms 175904 KB Output is correct
15 Correct 1567 ms 176104 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 678 ms 78660 KB Output is correct
3 Correct 1058 ms 108260 KB Output is correct
4 Correct 1557 ms 176180 KB Output is correct
5 Correct 1580 ms 175852 KB Output is correct
6 Correct 1606 ms 118060 KB Output is correct
7 Correct 61 ms 11348 KB Output is correct
8 Correct 744 ms 65124 KB Output is correct
9 Correct 1228 ms 92576 KB Output is correct
10 Correct 2330 ms 175908 KB Output is correct
11 Correct 2413 ms 181592 KB Output is correct
12 Correct 2204 ms 181404 KB Output is correct
13 Correct 1993 ms 181492 KB Output is correct
14 Correct 2184 ms 181416 KB Output is correct
15 Correct 1407 ms 181132 KB Output is correct
16 Correct 2077 ms 181292 KB Output is correct
17 Correct 2784 ms 181480 KB Output is correct
18 Correct 2749 ms 181960 KB Output is correct
19 Correct 2880 ms 184152 KB Output is correct
20 Correct 2643 ms 184192 KB Output is correct
21 Correct 3058 ms 184160 KB Output is correct
22 Correct 2932 ms 184492 KB Output is correct
23 Correct 2973 ms 184464 KB Output is correct
24 Correct 1484 ms 184180 KB Output is correct
25 Correct 2330 ms 184468 KB Output is correct

Subtask #4
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 5 ms 860 KB Output is correct
7 Correct 4 ms 860 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 5 ms 1372 KB Output is correct
11 Correct 6 ms 1528 KB Output is correct
12 Correct 7 ms 1372 KB Output is correct
13 Correct 7 ms 1372 KB Output is correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 8 ms 2396 KB Output is correct
17 Correct 8 ms 2396 KB Output is correct
18 Correct 8 ms 2396 KB Output is correct
19 Correct 5 ms 1516 KB Output is correct
20 Correct 9 ms 2396 KB Output is correct
21 Correct 8 ms 1372 KB Output is correct
22 Correct 8 ms 2396 KB Output is correct
23 Correct 9 ms 1584 KB Output is correct
24 Correct 8 ms 2396 KB Output is correct
25 Correct 7 ms 1560 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 ms 432 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1492 ms 86064 KB Output is correct
30 Correct 734 ms 86192 KB Output is correct
31 Correct 1690 ms 100168 KB Output is correct
32 Correct 814 ms 86732 KB Output is correct
33 Correct 2120 ms 118556 KB Output is correct
34 Correct 1535 ms 179412 KB Output is correct
35 Correct 2289 ms 118476 KB Output is correct
36 Correct 1626 ms 179284 KB Output is correct
37 Correct 689 ms 78512 KB Output is correct
38 Correct 946 ms 108280 KB Output is correct
39 Correct 1554 ms 175904 KB Output is correct
40 Correct 1567 ms 176104 KB Output is correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 678 ms 78660 KB Output is correct
43 Correct 1058 ms 108260 KB Output is correct
44 Correct 1557 ms 176180 KB Output is correct
45 Correct 1580 ms 175852 KB Output is correct
46 Correct 1606 ms 118060 KB Output is correct
47 Correct 61 ms 11348 KB Output is correct
48 Correct 744 ms 65124 KB Output is correct
49 Correct 1228 ms 92576 KB Output is correct
50 Correct 2330 ms 175908 KB Output is correct
51 Correct 2413 ms 181592 KB Output is correct
52 Correct 2204 ms 181404 KB Output is correct
53 Correct 1993 ms 181492 KB Output is correct
54 Correct 2184 ms 181416 KB Output is correct
55 Correct 1407 ms 181132 KB Output is correct
56 Correct 2077 ms 181292 KB Output is correct
57 Correct 2784 ms 181480 KB Output is correct
58 Correct 2749 ms 181960 KB Output is correct
59 Correct 2880 ms 184152 KB Output is correct
60 Correct 2643 ms 184192 KB Output is correct
61 Correct 3058 ms 184160 KB Output is correct
62 Correct 2932 ms 184492 KB Output is correct
63 Correct 2973 ms 184464 KB Output is correct
64 Correct 1484 ms 184180 KB Output is correct
65 Correct 2330 ms 184468 KB Output is correct
66 Correct 1008 ms 95236 KB Output is correct
67 Correct 1377 ms 110904 KB Output is correct
68 Correct 1736 ms 128360 KB Output is correct
69 Correct 1683 ms 117856 KB Output is correct
70 Correct 1688 ms 184512 KB Output is correct
71 Correct 1990 ms 184468 KB Output is correct
72 Correct 2190 ms 184408 KB Output is correct
73 Correct 2378 ms 184924 KB Output is correct
74 Correct 119 ms 12956 KB Output is correct
75 Correct 217 ms 21640 KB Output is correct
76 Correct 2645 ms 345964 KB Output is correct
77 Correct 2613 ms 343796 KB Output is correct
78 Correct 2613 ms 343708 KB Output is correct
79 Correct 2323 ms 184684 KB Output is correct
80 Correct 2681 ms 337880 KB Output is correct
81 Correct 2170 ms 184888 KB Output is correct
82 Correct 2654 ms 343472 KB Output is correct
83 Correct 2631 ms 184892 KB Output is correct
84 Correct 2721 ms 343824 KB Output is correct
85 Correct 2799 ms 185496 KB Output is correct
86 Correct 2687 ms 343700 KB Output is correct
87 Correct 2748 ms 185172 KB Output is correct
88 Correct 2677 ms 343704 KB Output is correct
89 Correct 2304 ms 265852 KB Output is correct