제출 #282985

#제출 시각아이디문제언어결과실행 시간메모리
282985dolphingarlicMonkey and Apple-trees (IZhO12_apple)C++14
0 / 100
515 ms262148 KiB
#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 ret = 0;
        if (lc) ret += lc->query(a, b);
        if (rc) ret += rc->query(a, b);
        return ret;
    }
};
 
Node *root = new Node();
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int m, c = 0, d, x, y;
    cin >> m;
    while (m--) {
        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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...