Submission #1296034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296034		MinhKien	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	298 ms	137540 KiB

apple

#include <iostream>

using namespace std;

int n, t, l, r, last;

struct SEG {
    struct node {
        int val;
        bool lazy;
        node *l, *r;

        node () {
            val = 0;
            lazy = false;
            l = r = nullptr;
        }
    };

    node *root;

    SEG () {
        root = new node();
    }

    int get(node *t) {
        return t ? t->val : 0;
    }

    void down(node *cur, int l, int r) {
        if (!cur->lazy) return;

        cur->lazy = false;

        int mid = (l + r) >> 1;

        if (!cur->l) cur->l = new node();
        cur->l->val = mid - l + 1;
        cur->l->lazy = true;

        if (!cur->r) cur->r = new node();
        cur->r->val = r - mid;
        cur->r->lazy = true;
    }

    void update(int u, int v, node *cur, int l = 1, int r = 1e9) {
        if (l >= u && r <= v) {
            cur->val = r - l + 1;
            cur->lazy = true;
            return;
        }

        int mid = (l + r) >> 1;
        down(cur, l, r);

        if (mid >= u) {
            if (!cur->l) cur->l = new node();
            update(u, v, cur->l, l, mid);
        }

        if (mid + 1 <= v) {
            if (!cur->r) cur->r = new node();
            update(u, v, cur->r, mid + 1, r);
        }

        cur->val = get(cur->l) + get(cur->r);
    }

    int get(int u, int v, node *cur, int l = 1, int r = 1e9) {
        if (l > v || r < u) return 0;
        if (!cur) return 0;

        if (l >= u && r <= v) {
            return cur->val;
        }

        int mid = (l + r) >> 1;
        down(cur, l, r);
        return get(u, v, cur->l, l, mid) + get(u, v, cur->r, mid + 1, r);
    }
} seg;

int main() {
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n;
    while (n--) {
        cin >> t >> l >> r;

        l += last;
        r += last;

        if (t == 1) {
            last = seg.get(l, r, seg.root);
            cout << last << "\n";
        } else {
            seg.update(l, r, seg.root);
        }
    }

    return 0;
}

• Subtask 1: 100 / 100