Submission #1257716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257716		Turkhuu	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	206 ms	97988 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 {
    int l = 0, r = 0, cnt = 0;
    bool all = 0;
    S() {}
    S(int cnt, bool all) : cnt{cnt}, all{all} {}
    void make_all(int _cnt) {
        all = 1, cnt = _cnt;
    }
};
const int M = 2e5 + 5;
int N = 1;
S s[M * 31];
int shine(int cnt = 0, bool all = 0) {
    return s[++N] = S(cnt, all), N;
}
void push(int i, int l, int r) {
    if (!s[i].l) s[i].l = shine();
    if (!s[i].r) s[i].r = shine();
    if (!s[i].all) return;
    int m = (l + r) / 2;
    s[s[i].l].make_all(m - l + 1);
    s[s[i].r].make_all(r - m);
}
void upd(int i, int l, int r, int L, int R) {
    if (R < l || r < L) return;
    if (L <= l && r <= R) {s[i].make_all(r - l + 1); return;}
    push(i, l, r);
    int m = (l + r) / 2;
    upd(s[i].l, l, m, L, R);
    upd(s[i].r, m + 1, r, L, R);
    s[i].cnt = s[s[i].l].cnt + s[s[i].r].cnt;
}
int qry(int i, int l, int r, int L, int R) {
    if (R < l || r < L) return 0;
    if (L <= l && r <= R) return s[i].cnt;
    push(i, l, r);
    int m = (l + r) / 2;
    return qry(s[i].l, l, m, L, R) + qry(s[i].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(1, 1, 1e9, l, r)) << "\n";
        else upd(1, 1, 1e9, l, r);
    }
    return 6/22;
}

• Subtask 1: 100 / 100