제출 #1257724

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257724		Turkhuu	원숭이와 사과 나무 (IZhO12_apple)	C++20	100 / 100	27 ms	840 KiB

apple

#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
struct S {
    S* l = nullptr;
    S* r = nullptr;
    int cnt = 0;
};
S* root = new S{};
void shine(S* x) {
    if (x->l) return;
    x->l = new S{};
    x->r = new S{};
}
void upd(S* x, int l, int r, int L, int R) {
    if (R < l || r < L || x->cnt == r - l + 1) return;
    if (L <= l && r <= R) {x->cnt = r - l + 1; return;}
    shine(x);
    int m = (l + r) / 2;
    upd(x->l, l, m, L, R);
    upd(x->r, m + 1, r, L, R);
    x->cnt = x->l->cnt + x->r->cnt;
}
int qry(S* x, int l, int r, int L, int R) {
    if (R < l || r < L || !x->cnt) return 0;
    if (L <= l && r <= R) return x->cnt;
    if (x->cnt == r - l + 1) return min(r, R) - max(l, L) + 1;
    int m = (l + r) / 2;
    return qry(x->l, l, m, L, R) + qry(x->r, m + 1, r, L, R);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q, c = 0; cin >> q; while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        l += c, r += c;
        if (t == 1) cout << (c = qry(root, 1, 1e9, l, r)) << "\n";
        else upd(root, 1, 1e9, l, r);
    }
    return 6/22;
}

• Subtask 1: 100 / 100