제출 #1356008

#제출 시각아이디문제언어결과실행 시간메모리
1356008waygonz원숭이와 사과 나무 (IZhO12_apple)C++20
100 / 100
266 ms205672 KiB
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = (int)1e9;

struct SparseSegmentTree {
    struct Node {
        ll seg = 0, lz = 0;
        struct Node *left = nullptr, *right = nullptr;
    };
    Node *root = new Node;
    void apply(Node *u, int l, int r, int v) {
        if (v) u->lz = 1, u->seg = r - l + 1;
    }
    void push(Node *u, int l, int r) {
        if (!(u->left)) u->left = new Node;
        if (!(u->right)) u->right = new Node;
        int mid = (l + r) / 2;
        apply(u->left, l, mid, u->lz);
        apply(u->right, mid+1, r, u->lz);
    }
    void update(Node *u, int l, int r, int x, int y, int v) {
        if (x <= l && r <= y) return apply(u, l, r, v);
        push(u, l, r);
        int mid = (l + r) / 2;
        if (x <= mid) update(u->left, l, mid, x, y, v);
        if (y > mid) update(u->right, mid+1, r, x, y, v);
        u->seg = u->left->seg + u->right->seg;
    }
    ll query(Node *u, int l, int r, int x, int y) {
        if (x <= l && r <= y) return u->seg;
        push(u, l, r);
        int mid = (l + r) / 2;
        ll sum = 0;
        if (x <= mid) sum += query(u->left, l, mid, x, y);
        if (y > mid) sum += query(u->right, mid+1, r, x, y);
        return sum;
    }
};

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int m; cin >> m;
    int c = 0;
    struct SparseSegmentTree T;
    while (m--) {
        int t; cin >> t;
        if (t == 1) {
            int l, r;
            cin >> l >> r;
            c = T.query(T.root, 1, N, l + c, r + c);
            cout << c << '\n';
        } else {
            int l, r;
            cin >> l >> r;
            T.update(T.root, 1, N, l + c, r + c, 1);
        }
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…