제출 #1343835

#제출 시각아이디문제언어결과실행 시간메모리
1343835vpinx원숭이와 사과 나무 (IZhO12_apple)C++20
0 / 100
1 ms348 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e9;

struct node {
    int li, ri, sum, lazy;
    node *left = nullptr, *right = nullptr;
    node(int lb, int rb) {
        li = lb, ri = rb, sum = lazy = 0;
    }
    void extend() {
        if (!left and li != ri) {
            int mid = (li + ri) / 2;
            left = new node(li, mid);
            right = new node(mid + 1, ri);
        }
    }
    void push() {
        if (lazy != 0) {
            sum = (ri - li + 1);
            if (li != ri) left->lazy = right->lazy = 1;
        }
    }
    void add(int l, int r) {
        extend(); push();
        if (r < li or ri < l) return;
        if (l <= li and ri <= r) {
            lazy = 1;
            push();
            return;
        }
        left->add(l, r);
        right->add(l, r);
        sum = left->sum + right->sum;
    }
    int query(int l, int r) {
        extend(); push();
        if (r < li or ri < l) return 0;
        if (l <= li and ri <= r) return sum;
        return left->query(l, r) + right->query(l, r); 
    }
};

void solve() {
    int q;
    cin >> q;
    
    int c = 0;
    node root(0, N);
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        l += c - 1, r += c - 1;
        if (t == 1) {
            int ans = root.query(l, r);
            cout << ans << "\n";
            c += ans;
        }else root.add(l, r);
    }
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...