제출 #1330845

#제출 시각아이디문제언어결과실행 시간메모리
1330845JahonaliX원숭이와 사과 나무 (IZhO12_apple)C++20
100 / 100
53 ms47868 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long
constexpr int mod = 1e9 + 7, inf = 1e9, N = 2000000;

struct dynamic_segment_tree {
    int t[N], lf[N], rg[N], cr;
    dynamic_segment_tree() { t[0] = 0, lf[0] = -1, rg[0] = -1, cr = 1; }
    int new_node() {
        lf[cr] = -1, rg[cr] = -1, t[cr] = 0;
        return cr++;
    }
    void update(int L, int R, int v = 0, int l = 0, int r = inf) {
        if (L <= l && r <= R) t[v] = r - l + 1;
        else {
            if (t[v] == r - l + 1) return;
            int m = (l + r) >> 1;
            if (lf[v] == -1) lf[v] = new_node();
            if (rg[v] == -1) rg[v] = new_node();
            if (L <= m) update(L, R, lf[v], l, m);
            if (m < R) update(L, R, rg[v], m + 1, r);
            t[v] = t[lf[v]] + t[rg[v]];
        }
    }
    int get(int L, int R, int v = 0, int l = 0, int r = inf) {
        if (v == -1) return 0;
        if (L <= l && r <= R) return t[v];
        if (t[v] == r - l + 1) {
            return min(R, r) - max(l, L) + 1;
        }
        int m = (l + r) >> 1;
        if (R <= m) return get(L, R, lf[v], l, m);
        if (L > m) return get(L, R, rg[v], m + 1, r);
        return get(L, R, lf[v], l, m) + get(L, R, rg[v], m + 1, r);
    }
};

int32_t main() {
#ifdef JahonaliX
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int q, c = 0;
    cin >> q;
    dynamic_segment_tree s;
    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        l += c, r += c;
        if (type == 1) {
            c = s.get(l, r);
            cout << c << '\n';
        }
        else s.update(l, r);
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...