Submission #894680

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
894680	2023-12-28T17:00:33 Z	Tam_theguide	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	162 ms	153392 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	150612 KB	Output is correct
2	Correct	23 ms	150620 KB	Output is correct
3	Correct	24 ms	150608 KB	Output is correct
4	Correct	29 ms	150864 KB	Output is correct
5	Correct	30 ms	150876 KB	Output is correct
6	Correct	31 ms	150924 KB	Output is correct
7	Correct	30 ms	150932 KB	Output is correct
8	Correct	71 ms	151572 KB	Output is correct
9	Correct	132 ms	152828 KB	Output is correct
10	Correct	127 ms	152788 KB	Output is correct
11	Correct	140 ms	152780 KB	Output is correct
12	Correct	160 ms	152656 KB	Output is correct
13	Correct	120 ms	153168 KB	Output is correct
14	Correct	126 ms	153256 KB	Output is correct
15	Correct	159 ms	153392 KB	Output is correct
16	Correct	162 ms	153172 KB	Output is correct
17	Correct	120 ms	153168 KB	Output is correct
18	Correct	134 ms	153172 KB	Output is correct
19	Correct	159 ms	153168 KB	Output is correct
20	Correct	162 ms	153168 KB	Output is correct