Submission #1257724

#TimeUsernameProblemLanguageResultExecution timeMemory
1257724TurkhuuMonkey and Apple-trees (IZhO12_apple)C++20
100 / 100
27 ms840 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...