Submission #500749

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
500749	2022-01-01T07:16:00 Z	Jomnoi	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	424 ms	262148 KB

apple

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

class SegmentTree {
    public :
        int tree, lazy;
        int l, r;
        SegmentTree *L, *R;
        SegmentTree() {}
        SegmentTree(int left, int right) {
            tree = lazy = 0;
            l = left;
            r = right;
            L = R = NULL;
        }
};

void compute(SegmentTree *now) {
    int mid = (now->l + now->r) / 2;
    if(now->L == NULL) {
        now->L = new SegmentTree(now->l, mid);
    }
    if(now->R == NULL) {
        now->R = new SegmentTree(mid + 1, now->r);
    }
}

void push_lazy(SegmentTree *now) {
    if(!now->lazy) {
        return;
    }

    now->tree = now->r - now->l + 1;
    compute(now);
    if(now->l != now->r) {
        now->L->lazy = now->R->lazy = 1;
    }

    now->lazy = 0;
}

void update(SegmentTree *now, int ql, int qr) {
    push_lazy(now);
    if(now->r < ql || qr < now->l) {
        return;
    }
    if(ql <= now->l && now->r <= qr) {
        now->lazy = 1;
        push_lazy(now);
        return;
    }

    compute(now);
    update(now->L, ql, qr);
    update(now->R, ql, qr);
    now->tree = now->L->tree + now->R->tree;
}

int query(SegmentTree *now, int ql, int qr) {
    push_lazy(now);
    if(now->r < ql || qr < now->l) {
        return 0;
    }
    if(ql <= now->l && now->r <= qr) {
        return now->tree;
    }

    compute(now);
    return query(now->L, ql, qr) + query(now->R, ql, qr);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int m;
    cin >> m;
    int C = 0;
    SegmentTree *root = new SegmentTree(1, 1e9);
    while(m--) {
        int d, x, y;
        cin >> d >> x >> y;
        if(d == 2) {
            update(root, x + C, y + C);
        }
        else {
            C = query(root, x + C, y + C);
            cout << C << '\n';
        }
    }
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct
4	Correct	19 ms	9408 KB	Output is correct
5	Correct	33 ms	11456 KB	Output is correct
6	Correct	22 ms	11076 KB	Output is correct
7	Correct	22 ms	11448 KB	Output is correct
8	Correct	190 ms	87732 KB	Output is correct
9	Correct	362 ms	152240 KB	Output is correct
10	Correct	408 ms	168356 KB	Output is correct
11	Correct	411 ms	180828 KB	Output is correct
12	Correct	424 ms	186672 KB	Output is correct
13	Correct	372 ms	217160 KB	Output is correct
14	Correct	398 ms	219160 KB	Output is correct
15	Runtime error	412 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-