답안 #282736

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
282736	2020-08-24T19:50:30 Z	dolphingarlic	원숭이와 사과 나무 (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

#	결과	실행 시간	메모리	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	-