제출 #1340802

#제출 시각아이디문제언어결과실행 시간메모리
1340802kawhiet원숭이와 사과 나무 (IZhO12_apple)C++20
100 / 100
243 ms137372 KiB
#include <bits/stdc++.h>
using namespace std;

struct SparseSegmentTree {
    struct Node {
        int sum = 0;
        int lazy = 0;
        Node *left = nullptr;
        Node *right = nullptr;
    };

    int n;
    Node *root;

    SparseSegmentTree(int _n) {
        n = _n;
        root = new Node();
    }

    void apply(Node *cur, int len, int val) {
        cur -> lazy = val;
        cur -> sum = len * val;
    }

    void push(Node *cur, int l, int r) {
        if (cur -> lazy == 0) return;
        if (cur -> left == nullptr) cur -> left = new Node;
        if (cur -> right == nullptr) cur -> right = new Node;
        int m = (l + r) / 2;
        apply(cur -> left, m - l + 1, cur -> lazy);
        apply(cur -> right, r - m, cur -> lazy);
        cur -> lazy = 0;
    }

    void update(Node *cur, int tl, int tr, int l, int r, int v) {
        if (r < tl || tr < l) return;
        if (l <= tl && tr <= r) {
            apply(cur, tr - tl + 1, v);
            return;
        }
        push(cur, tl, tr);
        int tm = (tl + tr) / 2;
        if (cur -> left == nullptr) cur -> left = new Node; 
        if (cur -> right == nullptr) cur -> right = new Node; 
        update(cur -> left, tl, tm, l, r, v);
        update(cur -> right, tm + 1, tr, l, r, v);
        cur -> sum = cur -> left -> sum + cur -> right -> sum;
    }

    int get(Node *cur, int tl, int tr, int l, int r) {
        if (cur == nullptr) return 0;
        if (r < tl || tr < l) return 0;
        if (l <= tl && tr <= r) return cur -> sum;
        push(cur, tl, tr);
        int tm = (tl + tr) / 2;
        return get(cur -> left, tl, tm, l, r) + get(cur -> right, tm + 1, tr, l, r);
    }

    void update(int l, int r, int v) { update(root, 0, n - 1, l, r, v); }
    int get(int l, int r) { return get(root, 0, n - 1, l, r); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    int c = 0;
    SparseSegmentTree t(1e9 + 5);
    while (q--) {
        int k, l, r;
        cin >> k >> l >> r;
        if (k == 1) {
            c = t.get(c + l, c + r);
            cout << c << '\n';
        } else {
            t.update(c + l, c + r, 1);
        }
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...