Submission #282736

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
282736	2020-08-24T19:50:30 Z	dolphingarlic	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	551 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 = 1000000000):
        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) {
        if (a <= l && b >= r) {
            lazy = 1;
            push_lazy();
        } else {
            int mid = (l + r) / 2;
            if (a <= mid && b >= l) {
                if (!lc) lc = new Node(l, mid);
                lc->push_lazy();
                val -= lc->val;
                lc->update(a, b);
                val += lc->val;
            }
            if (a <= r && b > mid) {
                if (!rc) rc = new Node(mid + 1, r);
                rc->push_lazy();
                val -= rc->val;
                rc->update(a, b);
                val += rc->val;
            }
        }
    }

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    Node *root = new Node();
    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	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	21 ms	6784 KB	Output is correct
5	Correct	22 ms	8192 KB	Output is correct
6	Correct	23 ms	7936 KB	Output is correct
7	Correct	24 ms	8184 KB	Output is correct
8	Correct	186 ms	61176 KB	Output is correct
9	Correct	368 ms	104824 KB	Output is correct
10	Correct	391 ms	116888 KB	Output is correct
11	Correct	397 ms	126200 KB	Output is correct
12	Correct	406 ms	130424 KB	Output is correct
13	Correct	373 ms	157560 KB	Output is correct
14	Correct	375 ms	158968 KB	Output is correct
15	Runtime error	551 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-