Submission #1208724

#TimeUsernameProblemLanguageResultExecution timeMemory
1208724PakinDioxide원숭이와 사과 나무 (IZhO12_apple)C++17
0 / 100
349 ms327680 KiB
/*
    author  : PakinDioxide
    created : 27/05/2025 23:38
    task    : IZhO12_apple
*/
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll mxN = 1e9+5;

struct T {
    ll l, r, lz, val;
    T *u = nullptr, *v = nullptr;
    T(ll l_, ll r_) { l = l_, r = r_, val = lz = 0; }
    void add() {
        ll x = l + (r-l)/2;
        if (u == nullptr) u = new T(l, x);
        if (v == nullptr) v = new T(x+1, r);
    }
    void push() {
        if (lz) u->val = u->r-u->l+1, u->lz = 1, v->val = v->r-v->l+1, v->lz = 1, lz = 0;
    }
};

T *seg = new T(1, mxN);

void upd(int l, int r, int x, int y, T *g) {
    g->add();
    if (x <= l && r <= y) g->val = r-l+1, g->lz = 1, g->push();
    else {
        g->push();
        ll mid = l + (r-l)/2;
        if (mid >= x) upd(l, mid, x, y, g->u);
        if (mid+1 <= y) upd(mid+1, r, x, y, g->v);
        g->val = g->u->val + g->v->val;
    }
}

ll qr(int l, int r, int x, int y, T *g) {
    g->add();
    if (x <= l && r <= y) return g->val;
    else {
        g->push();
        ll mid = l + (r-l)/2, v = 0;
        if (mid >= x) v += qr(l, mid, x, y, g->u);
        if (mid+1 <= y) v += qr(mid+1, r, x, y, g->v);
        return v;
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int q; cin >> q; ll c = 0;
    while (q--) {
        int t; ll l, r; cin >> t >> l >> r;
        if (t == 1) cout << (c = qr(1, mxN, l+c, r+c, seg)) << '\n';
        else upd(1, mxN, l+c, r+c, seg);
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...