oj.uz

Submission #942132

# Submission time Handle Problem Language Result Execution time Memory
942132 2024-03-10T09:43:15 Z Pannda Ants and Sugar (JOI22_sugar) C++17
26 / 100
 3101 ms 186824 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);

    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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 4 ms 860 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 604 KB Output is correct
10 Correct 5 ms 1372 KB Output is correct
11 Correct 6 ms 1372 KB Output is correct
12 Correct 7 ms 1368 KB Output is correct
13 Correct 8 ms 1368 KB Output is correct
14 Runtime error 1 ms 604 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #2
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 Runtime error 1 ms 348 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 700 ms 78812 KB Output is correct
3 Correct 1004 ms 109260 KB Output is correct
4 Correct 1724 ms 185160 KB Output is correct
5 Correct 1682 ms 185272 KB Output is correct
6 Correct 1509 ms 125692 KB Output is correct
7 Correct 63 ms 12032 KB Output is correct
8 Correct 704 ms 68564 KB Output is correct
9 Correct 1231 ms 97944 KB Output is correct
10 Correct 2271 ms 186368 KB Output is correct
11 Correct 2448 ms 186356 KB Output is correct
12 Correct 2446 ms 186532 KB Output is correct
13 Correct 1969 ms 186732 KB Output is correct
14 Correct 2197 ms 186572 KB Output is correct
15 Correct 1449 ms 186128 KB Output is correct
16 Correct 1952 ms 186312 KB Output is correct
17 Correct 2597 ms 186824 KB Output is correct
18 Correct 2720 ms 186656 KB Output is correct
19 Correct 2798 ms 186672 KB Output is correct
20 Correct 2692 ms 186612 KB Output is correct
21 Correct 2896 ms 186608 KB Output is correct
22 Correct 3101 ms 186472 KB Output is correct
23 Correct 2856 ms 186624 KB Output is correct
24 Correct 1609 ms 186544 KB Output is correct
25 Correct 2902 ms 186508 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 4 ms 860 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 604 KB Output is correct
10 Correct 5 ms 1372 KB Output is correct
11 Correct 6 ms 1372 KB Output is correct
12 Correct 7 ms 1368 KB Output is correct
13 Correct 8 ms 1368 KB Output is correct
14 Runtime error 1 ms 604 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -