Submission #813514

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
813514	2023-08-07T19:25:15 Z	phi	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	446 ms	237872 KB

apple

#include <iostream>
#include <vector>

using namespace std;

struct Node {
    int l, r;
    int tl, tr;
    bool lazy;
    int t;
};

struct SparseSegTree {
    vector<Node> nodes;
    int cnt;

    SparseSegTree (int size) {
        nodes.resize(size);
        cnt = 0;
        insert(0, 1e9 + 2);
    }

    int insert(int l, int r) {
        nodes[cnt] = { -1, -1, l, r, false, 0 };
        return cnt++;
    }

    void push(Node &node) {
        if (!node.lazy) return;

        node.t = node.tr - node.tl;

        int mid = (node.tl + node.tr - 1) / 2;

        if (node.l == -1)
            node.l = insert(node.tl, mid + 1);
        if (node.r == -1)
            node.r = insert(mid + 1, node.tr);

        nodes[node.l].lazy = true;
        nodes[node.r].lazy = true;

        node.lazy = false;
    }

    void update(Node &node, int l, int r) {
        push(node);

        if (node.tl == l && node.tr == r) {
            node.lazy = true;
            push(node);
            return;
        }

        int mid = (node.tl + node.tr - 1) / 2;

        if (node.l == -1)
            node.l = insert(node.tl, mid + 1);
        if (node.r == -1)
            node.r = insert(mid + 1, node.tr);

        if (l >= mid + 1) {
            update(nodes[node.r], l, r);
        } else if (r <= mid + 1) {
            update(nodes[node.l], l, r);
        } else {
            update(nodes[node.l], l, mid + 1);
            update(nodes[node.r], mid + 1, r);
        }

        push(nodes[node.l]);
        push(nodes[node.r]);

        node.t = nodes[node.l].t + nodes[node.r].t;
    }

    int query(Node &node, int l, int r) {
        push(node);

        if (node.tl == l && node.tr == r)
            return node.t;

        int mid = (node.tl + node.tr - 1) / 2;

        if (node.l == -1)
            node.l = insert(node.tl, mid + 1);
        if (node.r == -1)
            node.r = insert(mid + 1, node.tr);

        if (l >= mid + 1) return query(nodes[node.r], l, r);
        if (r <= mid + 1) return query(nodes[node.l], l, r);
        return query(nodes[node.l], l, mid + 1) + query(nodes[node.r], mid + 1, r);
    }
};

int main() {
    int m;
    cin >> m;
    int c = 0;

    SparseSegTree tree(1e7);

    while (m--) {
        int d, x, y;
        cin >> d >> x >> y;

        if (d == 1) {
            c = tree.query(tree.nodes[0], x + c, y + c + 1);
            cout << c << "\n";
        } else {
            tree.update(tree.nodes[0], x + c, y + c + 1);
        }
    }

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	91 ms	235084 KB	Output is correct
2	Correct	84 ms	235040 KB	Output is correct
3	Correct	91 ms	235036 KB	Output is correct
4	Correct	103 ms	235188 KB	Output is correct
5	Correct	104 ms	235300 KB	Output is correct
6	Correct	104 ms	235272 KB	Output is correct
7	Correct	107 ms	235232 KB	Output is correct
8	Correct	202 ms	236172 KB	Output is correct
9	Correct	346 ms	237220 KB	Output is correct
10	Correct	355 ms	237284 KB	Output is correct
11	Correct	353 ms	237252 KB	Output is correct
12	Correct	361 ms	237204 KB	Output is correct
13	Correct	324 ms	237680 KB	Output is correct
14	Correct	338 ms	237872 KB	Output is correct
15	Correct	398 ms	237660 KB	Output is correct
16	Correct	420 ms	237732 KB	Output is correct
17	Correct	360 ms	237648 KB	Output is correct
18	Correct	328 ms	237700 KB	Output is correct
19	Correct	416 ms	237772 KB	Output is correct
20	Correct	446 ms	237776 KB	Output is correct