Submission #790534

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
790534	2023-07-22T19:58:07 Z	Blagoj	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	317 ms	188504 KB

apple

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

struct Node {
    int sum, lazy, tl, tr, l, r;
    Node() : sum(0), lazy(0), l(0), r(0) {}
} tree[64 * 123456];

int cnt = 1;

void push(int k) {
    if (tree[k].lazy) {
        tree[k].sum = tree[k].tr - tree[k].tl + 1;
        int m = (tree[k].tl + tree[k].tr) / 2; 
        if (tree[k].l == 0) {
            tree[k].l = ++cnt;
            tree[cnt].tl = tree[k].tl;
            tree[cnt].tr = m;
        }
        if (tree[k].r == 0) {
            tree[k].r = ++cnt;
            tree[cnt].tl = m + 1;
            tree[cnt].tr = tree[k].tr;
        }
        tree[tree[k].l].lazy = tree[tree[k].r].lazy = 1;
        tree[k].lazy = 0;
    }
}

void update(int k, int i, int j) {
    if (tree[k].tr < i || tree[k].tl > j) return;
    push(k);
    if (i <= tree[k].tl && tree[k].tr <= j) {
        tree[k].lazy = 1;
        push(k);
        return;
    }
    int m = (tree[k].tl + tree[k].tr) / 2;
    if (tree[k].l == 0) {
        tree[k].l = ++cnt;
        tree[cnt].tl = tree[k].tl;
        tree[cnt].tr = m;
    }
    if (tree[k].r == 0) {
        tree[k].r = ++cnt;
        tree[cnt].tl = m + 1;
        tree[cnt].tr = tree[k].tr;
    }
    update(tree[k].l, i, j);
    update(tree[k].r, i, j);
    push(tree[k].l);
    push(tree[k].r);
    tree[k].sum = tree[tree[k].l].sum + tree[tree[k].r].sum;
}

int query(int k, int i, int j) {
    if (tree[k].tr < i || tree[k].tl > j) return 0;
    push(k);
    if (i <= tree[k].tl && tree[k].tr <= j) return tree[k].sum;
    int m = (tree[k].tl + tree[k].tr) / 2;
    if (tree[k].l == 0) {
        tree[k].l = ++cnt;
        tree[cnt].tl = tree[k].tl;
        tree[cnt].tr = m;
    }
    if (tree[k].r == 0) {
        tree[k].r = ++cnt;
        tree[cnt].tl = m + 1;
        tree[cnt].tr = tree[k].tr;
    }
    return query(tree[k].l, i, j) + query(tree[k].r, i, j);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int q;
    cin >> q;
    int c = 0;
    tree[1].sum = tree[1].lazy = 0;
    tree[1].tl = 1;
    tree[1].tr = 1e9;
    while (q--) {
        int d, x, y;
        cin >> d >> x >> y;
        if (d == 1) {
            c = query(1, x + c, y + c);
            cout << c << endl;
        }
        else update(1, x + c, y + c);
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	185804 KB	Output is correct
2	Correct	68 ms	185944 KB	Output is correct
3	Correct	65 ms	185792 KB	Output is correct
4	Correct	72 ms	185860 KB	Output is correct
5	Correct	76 ms	185868 KB	Output is correct
6	Correct	78 ms	185788 KB	Output is correct
7	Correct	77 ms	185816 KB	Output is correct
8	Correct	155 ms	186008 KB	Output is correct
9	Correct	245 ms	186160 KB	Output is correct
10	Correct	248 ms	186148 KB	Output is correct
11	Correct	264 ms	186380 KB	Output is correct
12	Correct	254 ms	186176 KB	Output is correct
13	Correct	221 ms	186332 KB	Output is correct
14	Correct	309 ms	186528 KB	Output is correct
15	Correct	310 ms	188484 KB	Output is correct
16	Correct	317 ms	188504 KB	Output is correct
17	Correct	226 ms	188412 KB	Output is correct
18	Correct	228 ms	188396 KB	Output is correct
19	Correct	316 ms	188468 KB	Output is correct
20	Correct	302 ms	188484 KB	Output is correct