Submission #813514

#	Time	Username	Problem	Language	Result	Execution time	Memory
813514		phi	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	446 ms	237872 KiB

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 / 100