Submission #790531

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
790531	2023-07-22T19:45:30 Z	Blagoj	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	455 ms	262144 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) {
    push(k);
    if (tree[k].tr < i || tree[k].tl > j) return;
    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);
    tree[k].sum = tree[tree[k].l].sum + tree[tree[k].r].sum;
}

int query(int k, int i, int j) {
    push(k);
    if (tree[k].tr < i || tree[k].tl > j) return 0;
    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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	185748 KB	Output is correct
2	Correct	69 ms	185824 KB	Output is correct
3	Correct	66 ms	185772 KB	Output is correct
4	Correct	75 ms	185904 KB	Output is correct
5	Correct	85 ms	185932 KB	Output is correct
6	Correct	92 ms	186044 KB	Output is correct
7	Correct	77 ms	185932 KB	Output is correct
8	Correct	147 ms	186836 KB	Output is correct
9	Correct	282 ms	187976 KB	Output is correct
10	Correct	255 ms	188044 KB	Output is correct
11	Correct	275 ms	188012 KB	Output is correct
12	Correct	252 ms	187976 KB	Output is correct
13	Correct	225 ms	188404 KB	Output is correct
14	Correct	244 ms	188360 KB	Output is correct
15	Runtime error	455 ms	262144 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-