oj.uz

Submission #942072

# Submission time Handle Problem Language Result Execution time Memory
942072 2024-03-10T08:01:08 Z Pannda Ants and Sugar (JOI22_sugar) C++17
6 / 100
 4000 ms 126220 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);
    nodes.reserve(10000000);

    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;
            }
//            cout << idx << ' ' << l << ' ' << r << ": " << nodes[idx].ln << ' ' << nodes[idx].rn << ' ' << nodes[idx].ant << ' ' << nodes[idx].sugar << '\n' << "       " <<
//                                  nodes[idx].mn[0][0] << ' ' << nodes[idx].mn[0][1] << ' ' << nodes[idx].mn[1][0] << ' ' << nodes[idx].mn[1][1] << '\n';
        };
        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 348 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 344 KB Output is correct
6 Correct 38 ms 1368 KB Output is correct
7 Correct 33 ms 1444 KB Output is correct
8 Correct 19 ms 1124 KB Output is correct
9 Correct 18 ms 1112 KB Output is correct
10 Correct 110 ms 30728 KB Output is correct
11 Correct 105 ms 31060 KB Output is correct
12 Correct 109 ms 32596 KB Output is correct
13 Correct 119 ms 31540 KB Output is correct
14 Correct 158 ms 41440 KB Output is correct
15 Correct 157 ms 40276 KB Output is correct
16 Correct 60 ms 23892 KB Output is correct
17 Correct 61 ms 23376 KB Output is correct
18 Correct 59 ms 22980 KB Output is correct
19 Correct 117 ms 31480 KB Output is correct
20 Correct 60 ms 23232 KB Output is correct
21 Correct 112 ms 29780 KB Output is correct
22 Correct 62 ms 23124 KB Output is correct
23 Correct 110 ms 29904 KB Output is correct
24 Correct 59 ms 23456 KB Output is correct
25 Correct 73 ms 20528 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 0 ms 348 KB Output is correct
4 Execution timed out 4104 ms 126220 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 Execution timed out 4042 ms 90648 KB Time limit exceeded
3 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 348 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 344 KB Output is correct
6 Correct 38 ms 1368 KB Output is correct
7 Correct 33 ms 1444 KB Output is correct
8 Correct 19 ms 1124 KB Output is correct
9 Correct 18 ms 1112 KB Output is correct
10 Correct 110 ms 30728 KB Output is correct
11 Correct 105 ms 31060 KB Output is correct
12 Correct 109 ms 32596 KB Output is correct
13 Correct 119 ms 31540 KB Output is correct
14 Correct 158 ms 41440 KB Output is correct
15 Correct 157 ms 40276 KB Output is correct
16 Correct 60 ms 23892 KB Output is correct
17 Correct 61 ms 23376 KB Output is correct
18 Correct 59 ms 22980 KB Output is correct
19 Correct 117 ms 31480 KB Output is correct
20 Correct 60 ms 23232 KB Output is correct
21 Correct 112 ms 29780 KB Output is correct
22 Correct 62 ms 23124 KB Output is correct
23 Correct 110 ms 29904 KB Output is correct
24 Correct 59 ms 23456 KB Output is correct
25 Correct 73 ms 20528 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Execution timed out 4104 ms 126220 KB Time limit exceeded
30 Halted 0 ms 0 KB -