제출 #282736

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
282736		dolphingarlic	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	551 ms	262148 KiB

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