Submission #282740

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
282740	2020-08-24T19:57:13 Z	dolphingarlic	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	502 ms	262148 KB

apple

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

struct Node {
    int l, r, val;
    bool lazy;
    Node *lc, *rc;

    Node(int L = 1, int R = 1e9):
        l(L), r(R), val(0), lazy(false), lc(nullptr), rc(nullptr) {}
    
    void push_lazy() {
        if (!lazy) return;
        val = r - l + 1;
        lazy = 0;
        if (l != r) {
            int mid = (l + r) / 2;
            if (!lc) lc = new Node(l, mid);
            if (!rc) rc = new Node(mid + 1, r);
            lc->lazy = rc->lazy = 1;
        }
    }

    void update(int a, int b) {
        push_lazy();
        if (a > r || b < l) return;
        if (a <= l && b >= r) {
            lazy = 1;
            push_lazy();
        } else {
            int mid = (l + r) / 2;
            if (!lc) lc = new Node(l, mid);
            if (!rc) rc = new Node(mid + 1, r);
            lc->update(a, b);
            rc->update(a, b);
            val = lc->val + rc->val;
        }
    }

    int query(int a, int b) {
        push_lazy();
        if (a > r || b < l) return 0;
        if (a <= l && b >= r) return val;
        int mid = (l + r) / 2;
        if (!lc) lc = new Node(l, mid);
        if (!rc) rc = new Node(mid + 1, r);
        return lc->query(a, b) + rc->query(a, b);
    }
};

Node *root = new Node();

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

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	27 ms	8576 KB	Output is correct
5	Correct	27 ms	10488 KB	Output is correct
6	Correct	26 ms	9976 KB	Output is correct
7	Correct	26 ms	10360 KB	Output is correct
8	Correct	220 ms	77176 KB	Output is correct
9	Correct	424 ms	131192 KB	Output is correct
10	Correct	440 ms	147064 KB	Output is correct
11	Correct	467 ms	159352 KB	Output is correct
12	Correct	468 ms	165112 KB	Output is correct
13	Correct	454 ms	205176 KB	Output is correct
14	Correct	447 ms	207096 KB	Output is correct
15	Runtime error	502 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-