oj.uz

Submission #942136

# Submission time Handle Problem Language Result Execution time Memory
942136 2024-03-10T09:46:11 Z Pannda Ants and Sugar (JOI22_sugar) C++17
100 / 100
 3189 ms 351028 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();

    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 + 123);

    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 600 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 5 ms 1372 KB Output is correct
11 Correct 7 ms 1512 KB Output is correct
12 Correct 7 ms 1372 KB Output is correct
13 Correct 7 ms 1548 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 8 ms 2316 KB Output is correct
17 Correct 9 ms 2396 KB Output is correct
18 Correct 9 ms 2392 KB Output is correct
19 Correct 5 ms 1372 KB Output is correct
20 Correct 8 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 13 ms 1584 KB Output is correct
24 Correct 8 ms 2392 KB Output is correct
25 Correct 7 ms 1372 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1362 ms 86064 KB Output is correct
5 Correct 700 ms 86352 KB Output is correct
6 Correct 1582 ms 100148 KB Output is correct
7 Correct 697 ms 91540 KB Output is correct
8 Correct 1992 ms 127632 KB Output is correct
9 Correct 1530 ms 188624 KB Output is correct
10 Correct 2107 ms 127568 KB Output is correct
11 Correct 1530 ms 188684 KB Output is correct
12 Correct 655 ms 82596 KB Output is correct
13 Correct 950 ms 113872 KB Output is correct
14 Correct 1554 ms 185492 KB Output is correct
15 Correct 1570 ms 185084 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 663 ms 78584 KB Output is correct
3 Correct 951 ms 108328 KB Output is correct
4 Correct 1565 ms 176108 KB Output is correct
5 Correct 1531 ms 176164 KB Output is correct
6 Correct 1563 ms 118548 KB Output is correct
7 Correct 65 ms 11356 KB Output is correct
8 Correct 697 ms 64980 KB Output is correct
9 Correct 1186 ms 92592 KB Output is correct
10 Correct 2177 ms 175780 KB Output is correct
11 Correct 2328 ms 175724 KB Output is correct
12 Correct 2365 ms 175812 KB Output is correct
13 Correct 1993 ms 175880 KB Output is correct
14 Correct 2241 ms 176032 KB Output is correct
15 Correct 1460 ms 175504 KB Output is correct
16 Correct 1979 ms 175760 KB Output is correct
17 Correct 2745 ms 175932 KB Output is correct
18 Correct 3034 ms 175988 KB Output is correct
19 Correct 2924 ms 175788 KB Output is correct
20 Correct 2848 ms 176204 KB Output is correct
21 Correct 2944 ms 176124 KB Output is correct
22 Correct 3189 ms 175988 KB Output is correct
23 Correct 2958 ms 175944 KB Output is correct
24 Correct 1595 ms 175880 KB Output is correct
25 Correct 2536 ms 176344 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 600 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 5 ms 1372 KB Output is correct
11 Correct 7 ms 1512 KB Output is correct
12 Correct 7 ms 1372 KB Output is correct
13 Correct 7 ms 1548 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 8 ms 2316 KB Output is correct
17 Correct 9 ms 2396 KB Output is correct
18 Correct 9 ms 2392 KB Output is correct
19 Correct 5 ms 1372 KB Output is correct
20 Correct 8 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 13 ms 1584 KB Output is correct
24 Correct 8 ms 2392 KB Output is correct
25 Correct 7 ms 1372 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1362 ms 86064 KB Output is correct
30 Correct 700 ms 86352 KB Output is correct
31 Correct 1582 ms 100148 KB Output is correct
32 Correct 697 ms 91540 KB Output is correct
33 Correct 1992 ms 127632 KB Output is correct
34 Correct 1530 ms 188624 KB Output is correct
35 Correct 2107 ms 127568 KB Output is correct
36 Correct 1530 ms 188684 KB Output is correct
37 Correct 655 ms 82596 KB Output is correct
38 Correct 950 ms 113872 KB Output is correct
39 Correct 1554 ms 185492 KB Output is correct
40 Correct 1570 ms 185084 KB Output is correct
41 Correct 0 ms 344 KB Output is correct
42 Correct 663 ms 78584 KB Output is correct
43 Correct 951 ms 108328 KB Output is correct
44 Correct 1565 ms 176108 KB Output is correct
45 Correct 1531 ms 176164 KB Output is correct
46 Correct 1563 ms 118548 KB Output is correct
47 Correct 65 ms 11356 KB Output is correct
48 Correct 697 ms 64980 KB Output is correct
49 Correct 1186 ms 92592 KB Output is correct
50 Correct 2177 ms 175780 KB Output is correct
51 Correct 2328 ms 175724 KB Output is correct
52 Correct 2365 ms 175812 KB Output is correct
53 Correct 1993 ms 175880 KB Output is correct
54 Correct 2241 ms 176032 KB Output is correct
55 Correct 1460 ms 175504 KB Output is correct
56 Correct 1979 ms 175760 KB Output is correct
57 Correct 2745 ms 175932 KB Output is correct
58 Correct 3034 ms 175988 KB Output is correct
59 Correct 2924 ms 175788 KB Output is correct
60 Correct 2848 ms 176204 KB Output is correct
61 Correct 2944 ms 176124 KB Output is correct
62 Correct 3189 ms 175988 KB Output is correct
63 Correct 2958 ms 175944 KB Output is correct
64 Correct 1595 ms 175880 KB Output is correct
65 Correct 2536 ms 176344 KB Output is correct
66 Correct 980 ms 96276 KB Output is correct
67 Correct 1446 ms 111928 KB Output is correct
68 Correct 1920 ms 129768 KB Output is correct
69 Correct 1661 ms 119356 KB Output is correct
70 Correct 1738 ms 189512 KB Output is correct
71 Correct 2080 ms 189668 KB Output is correct
72 Correct 2224 ms 189380 KB Output is correct
73 Correct 2316 ms 190040 KB Output is correct
74 Correct 133 ms 17964 KB Output is correct
75 Correct 227 ms 26680 KB Output is correct
76 Correct 2759 ms 351028 KB Output is correct
77 Correct 2831 ms 348664 KB Output is correct
78 Correct 2888 ms 348740 KB Output is correct
79 Correct 2288 ms 189996 KB Output is correct
80 Correct 2851 ms 349060 KB Output is correct
81 Correct 2271 ms 189864 KB Output is correct
82 Correct 2757 ms 348484 KB Output is correct
83 Correct 2769 ms 189660 KB Output is correct
84 Correct 2805 ms 349128 KB Output is correct
85 Correct 2842 ms 190608 KB Output is correct
86 Correct 2776 ms 348700 KB Output is correct
87 Correct 2841 ms 189884 KB Output is correct
88 Correct 2718 ms 348616 KB Output is correct
89 Correct 2429 ms 270932 KB Output is correct