Submission #1283655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283655		VMaksimoski008	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	415 ms	230560 KiB

apple

#include <bits/stdc++.h>
using namespace std;

struct node {
    node *lc, *rc;
    int sum = 0, lazy = 0;

    node(int _s = 0) : sum(_s), lc(nullptr), rc(nullptr) {}

    node(node *lc, node *rc) : lc(lc), rc(rc) {
        if(lc) sum += lc->sum;
        if(rc) sum += rc->sum;
    }

    void ext() {
        if(!lc) {
            lc = new node();
            lc->lazy = lazy;
        }
        if(!rc) {
            rc = new node();
            rc->lazy = lazy;
        }
    }

    void push(int tl, int tr) {
        if(!lazy) return ;
        sum = tr - tl + 1;

        if(tl != tr) {
            ext();
            lc->lazy = 1;
            rc->lazy = 1;
        }

        lazy = 0;
    }

    void update(int tl, int tr, int l, int r) {
        push(tl, tr);
        if(tl > r || l > tr) return ;

        if(l <= tl && tr <= r) {
            lazy = 1;
            push(tl, tr);
            return ;
        }

        ext();
        int tm = (tl + tr) / 2;
        lc->update(tl, tm, l, r);
        rc->update(tm+1, tr, l, r);
        sum = lc->sum + rc->sum;
    }

    int query(int tl, int tr, int l, int r) {
        if(tl > r || l > tr) return 0;
        push(tl, tr);
        if(l <= tl && tr <= r) return sum;
        ext();
        int tm = (tl + tr) / 2;
        return lc->query(tl, tm, l, r) + rc->query(tm+1, tr, l, r);
    }
};

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

    node *sgt = new node();
    int n = 1e9, q; cin >> q;

    int lst = 0;
    while(q--) {
        int t, l, r; cin >> t >> l >> r;

        if(t == 1) {
            cout << (lst = sgt->query(1, n, l+lst, r+lst)) << '\n';
        } else {
            sgt->update(1, n, l+lst, r+lst);
        }
    }
}

• Subtask 1: 100 / 100