Submission #894680

#	Time	Username	Problem	Language	Result	Execution time	Memory
894680		Tam_theguide	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	162 ms	153392 KiB

apple

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int INF = 1e9;
struct node {
    int v, lazy, l, r, tl, tr;
    node() : v(0), lazy(0), l(-1), r(-1) {}
} seg[64*N];
int cnt;
void push(int root) {
    seg[root].v = (seg[root].tr - seg[root].tl + 1);
    seg[root].lazy = 1;
}

void update(int root, int tl, int tr, int l, int r) {
    if (tl > r || tr < l) return;
    if (tl >= l && tr <= r) {
        push(root);
        return;
    }
    int tm = (tl + tr) / 2;
    if (seg[root].l == -1) {
        seg[root].l = ++cnt;
        seg[seg[root].l].tl = tl;
        seg[seg[root].l].tr = tm;
    }

    if (seg[root].r == -1) {
        seg[root].r = ++cnt;
        seg[seg[root].r].tl = tm+1;
        seg[seg[root].r].tr = tr;
    }
    if (seg[root].lazy)
        push(seg[root].l), push(seg[root].r), seg[root].lazy = 0;
    update(seg[root].l, tl, tm, l, r);
    update(seg[root].r, tm+1, tr, l, r);
    seg[root].v = seg[seg[root].l].v + seg[seg[root].r].v;
}

int get(int root, int tl, int tr, int l, int r) {
    if (tl > r || tr < l) return 0;
    if (tl >= l && tr <= r) return seg[root].v;
    int tm = (tl + tr) / 2;
    if (seg[root].l == -1) {
        seg[root].l = ++cnt;
        seg[seg[root].l].tl = tl;
        seg[seg[root].l].tr = tm;
    }

    if (seg[root].r == -1) {
        seg[root].r = ++cnt;
        seg[seg[root].r].tl = tm+1;
        seg[seg[root].r].tr = tr;
    }
    if (seg[root].lazy)
        push(seg[root].l), push(seg[root].r), seg[root].lazy = 0;
    return get(seg[root].l, tl, tm, l, r) + get(seg[root].r, tm+1, tr, l, r);
}
int q;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> q;

    ++cnt;
    seg[1].tl = 0;
    seg[1].tr = INF;
    int c = 0;
    while (q--) {
        int cm, x, y;
        cin >> cm >> x >> y;
            x += c;
            y += c;
        if (cm == 1) {

            c = get(1, 0, INF, x, y);
            cout << c << '\n';
        } else {

            update(1, 0, INF, x, y);
        }
    }
}

• Subtask 1: 100 / 100