oj.uz

Submission #942070

# Submission time Handle Problem Language Result Execution time Memory
942070 2024-03-10T07:53:39 Z Pannda Ants and Sugar (JOI22_sugar) C++17
6 / 100
 4000 ms 144880 KB 
#include <bits/stdc++.h>
using namespace std;

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

    const int CL = 0, CR = 1e9 + 1;
    const long long INF = 1e18;

    struct Node {
        int ln = 0, rn = 0;
        long long ant = 0, sugar = 0, sugar2 = 0;
        long long lazy_sugar = 0, lazy_sugar2 = 0;
        vector<vector<long long>> mn = { { 0, 0 }, { 0, 0 } };
        Node operator+(Node b) {
            Node a = *this;
            Node res;
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    res.mn[i][j] = INF;
                    res.mn[i][j] = min(res.mn[i][j], a.mn[i][0] + b.mn[0][j]);
                    res.mn[i][j] = min(res.mn[i][j], a.mn[i][0] + b.mn[1][j]);
                    res.mn[i][j] = min(res.mn[i][j], a.mn[i][1] + b.mn[0][j]);
                    res.mn[i][j] = min(res.mn[i][j], a.mn[i][1] + b.mn[1][j] - a.sugar2);
                }
            }
            res.sugar2 = b.sugar2;
            return res;
        }
    };

    vector<Node> nodes(2);

    auto apply = [&](int &idx, long long delta_sugar, long long delta_sugar2) {
        if (idx == 0) {
            idx = nodes.size();
            nodes.emplace_back();
        }
        nodes[idx].sugar += delta_sugar;
        nodes[idx].sugar2 += delta_sugar2;
        nodes[idx].lazy_sugar += delta_sugar;
        nodes[idx].lazy_sugar2 += delta_sugar2;
        nodes[idx].mn[0][0] = min(0LL, nodes[idx].mn[0][0] + delta_sugar);
        nodes[idx].mn[0][1] += delta_sugar;
        nodes[idx].mn[1][0] += delta_sugar;
        nodes[idx].mn[1][1] += delta_sugar;
    };

    auto down = [&](int &idx) {
        if (idx == 0) {
            idx = nodes.size();
            nodes.emplace_back();
        } else {
            Node goat = nodes[idx];
            apply(goat.ln, goat.lazy_sugar, goat.lazy_sugar2);
            apply(goat.rn, goat.lazy_sugar, goat.lazy_sugar2);
            goat.lazy_sugar = 0;
            goat.lazy_sugar2 = 0;
            nodes[idx] = goat;
        }
    };

    auto addAnt = [&](int x, int delta) -> void {
        auto dfs = [&](auto self, int &idx, int l, int r) -> void {
            if (l + 1 == r) {
                if (idx == 0) {
                    idx = nodes.size();
                    nodes.emplace_back();
                }
                nodes[idx].ant += delta;
                nodes[idx].mn[0][0] = 0;
                nodes[idx].mn[0][1] = nodes[idx].mn[1][0] = INF;
                nodes[idx].mn[1][1] = - nodes[idx].ant + nodes[idx].sugar;
            } else {
                down(idx);
                int m = (l + r) >> 1;
                Node goat = nodes[idx];
                if (x < m) self(self, goat.ln, l, m);
                else self(self, goat.rn, m, r);
                int ln = goat.ln, rn = goat.rn;
                goat = nodes[goat.ln] + nodes[goat.rn];
                goat.ln = ln;
                goat.rn = rn;
                nodes[idx] = goat;
            }
        };
        int goat = 1;
        dfs(dfs, goat, CL, CR);
    };

    auto addSugar = [&](int ql, int qr, long long delta_sugar, long long delta_sugar2) -> void {
        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, delta_sugar2);
            down(idx);
            int m = (l + r) >> 1;
            Node goat = nodes[idx];
            self(self, goat.ln, l, m);
            self(self, goat.rn, m, r);
            int ln = goat.ln, rn = goat.rn;
            goat = nodes[goat.ln] + nodes[goat.rn];
            goat.ln = ln;
            goat.rn = rn;
            nodes[idx] = goat;
        };
        int goat = 1;
        dfs(dfs, goat, CL, CR);
    };

    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[1].mn[i][j]);
            }
        }
        return res;
    };

    int q, radius;
    cin >> q >> radius;
    long long total = 0;
    while (q--) {
        int type, x, c;
        cin >> type >> x >> c;
        if (type == 1) {
            addAnt(x, +c);
            total += c;
        }
        if (type == 2) {
            addSugar(x - radius, x + radius + 1, +c, 0);
            addSugar(x - radius, x + radius, 0, +c);
        }
        cout << total + query() << '\n';
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 36 ms 1584 KB Output is correct
7 Correct 32 ms 1600 KB Output is correct
8 Correct 18 ms 1480 KB Output is correct
9 Correct 17 ms 1480 KB Output is correct
10 Correct 101 ms 35532 KB Output is correct
11 Correct 108 ms 35576 KB Output is correct
12 Correct 117 ms 36028 KB Output is correct
13 Correct 110 ms 37180 KB Output is correct
14 Correct 153 ms 41396 KB Output is correct
15 Correct 154 ms 40780 KB Output is correct
16 Correct 62 ms 22716 KB Output is correct
17 Correct 60 ms 21952 KB Output is correct
18 Correct 60 ms 23448 KB Output is correct
19 Correct 106 ms 36352 KB Output is correct
20 Correct 71 ms 22976 KB Output is correct
21 Correct 115 ms 35520 KB Output is correct
22 Correct 60 ms 22008 KB Output is correct
23 Correct 112 ms 36028 KB Output is correct
24 Correct 60 ms 22468 KB Output is correct
25 Correct 75 ms 21144 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Execution timed out 4070 ms 144880 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 3880 ms 94384 KB Output is correct
3 Execution timed out 4035 ms 143928 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 36 ms 1584 KB Output is correct
7 Correct 32 ms 1600 KB Output is correct
8 Correct 18 ms 1480 KB Output is correct
9 Correct 17 ms 1480 KB Output is correct
10 Correct 101 ms 35532 KB Output is correct
11 Correct 108 ms 35576 KB Output is correct
12 Correct 117 ms 36028 KB Output is correct
13 Correct 110 ms 37180 KB Output is correct
14 Correct 153 ms 41396 KB Output is correct
15 Correct 154 ms 40780 KB Output is correct
16 Correct 62 ms 22716 KB Output is correct
17 Correct 60 ms 21952 KB Output is correct
18 Correct 60 ms 23448 KB Output is correct
19 Correct 106 ms 36352 KB Output is correct
20 Correct 71 ms 22976 KB Output is correct
21 Correct 115 ms 35520 KB Output is correct
22 Correct 60 ms 22008 KB Output is correct
23 Correct 112 ms 36028 KB Output is correct
24 Correct 60 ms 22468 KB Output is correct
25 Correct 75 ms 21144 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Execution timed out 4070 ms 144880 KB Time limit exceeded
30 Halted 0 ms 0 KB -