Submission #1257706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257706		Turkhuu	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	324 ms	137288 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;
    bool all = 0;
};
S* root = new S{};
void push(S* x, int l, int r) {
    if (!x->l) x->l = new S{};
    if (!x->r) x->r = new S{};
    if (!x->all) return;
    int m = (l + r) / 2;
    x->l->all = 1, x->l->cnt = m - l + 1;
    x->r->all = 1, x->r->cnt = r - m;
}
void upd(S* x, int l, int r, int L, int R) {
    if (R < l || r < L) return;
    if (L <= l && r <= R) {x->cnt = r - l + 1, x->all = 1; return;}
    push(x, l, r);
    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) return 0;
    if (L <= l && r <= R) return x->cnt;
    push(x, l, r);
    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