제출 #1198411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198411		khalwsh	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	398 ms	327680 KiB

apple

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll SZ = 1'000'000'000LL;

struct dynamicSeg {
    ll sum = 0;
    bool lazy = false;
    dynamicSeg *L = nullptr, *R = nullptr;

    void prop(ll nl, ll nr) {
        if (!lazy) return;
        // mark this node fully “ripe”
        sum = (nr - nl + 1);
        if (nl != nr) {
            if (!L) L = new dynamicSeg();
            if (!R) R = new dynamicSeg();
            L->lazy = R->lazy = true;
        }
        lazy = false;
    }

    void add(ll nl, ll nr, ll ql, ll qr) {
        prop(nl, nr);
        if (nl > qr || nr < ql) return;
        if (nl >= ql && nr <= qr) {
            // full cover: set the flag and immediately apply it
            lazy = true;
            prop(nl, nr);
            return;
        }
        ll mid = nl + (nr - nl) / 2;
        if (!L) L = new dynamicSeg();
        if (!R) R = new dynamicSeg();
        L->add(nl, mid, ql, qr);
        R->add(mid+1, nr, ql, qr);
        sum = L->sum + R->sum;
    }

    ll query(ll nl, ll nr, ll ql, ll qr) {
        prop(nl, nr);
        if (nl > qr || nr < ql) return 0;
        if (nl >= ql && nr <= qr) return sum;
        ll mid = nl + (nr - nl) / 2;
        ll leftSum  = L ? L->query(nl, mid, ql, qr) : 0;
        ll rightSum = R ? R->query(mid+1, nr, ql, qr) : 0;
        return leftSum + rightSum;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M;
    cin >> M;

    dynamicSeg dseg;
    ll C = 0;

    while(M--){
        int D;
        ll X, Y;
        cin >> D >> X >> Y;
        ll l = X + C;
        ll r = Y + C;
        // now 1 ≤ l,r ≤ 1e9 guaranteed

        if (D == 2) {
            dseg.add(1, SZ, l, r);
        } else {
            ll ans = dseg.query(1, SZ, l, r);
            cout << ans << "\n";
            C = ans;
        }
    }
    return 0;
}

• Subtask 1: 0 / 100