Submission #477488

#	Time	Username	Problem	Language	Result	Execution time	Memory
477488		Shin	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	126 ms	153328 KiB

apple

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7; // 998244353;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;

typedef long long ll;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

struct Node {
    int l, r, val;
    Node(int l = 0, int r = 0, int val = 0) : l(l), r(r), val(val) {
    }
};

struct segment_tree {
    vector<Node> t;
    int id = 1;
    int n;

    const int MAX = 2e5 + 7;

    segment_tree(int n) : n(n) {
        t.resize(MAX * 64);
    }

    void modify(int node, int l, int r, int u, int v) {
        if (t[node].val == r - l + 1) return;
        if (u <= l && r <= v) {
            t[node].val = r - l + 1;
        } else {
            int mid = (l + r) >> 1;
            if (u <= mid) {
                if (!t[node].l) t[node].l = ++ id;
                modify(t[node].l, l, mid, u, v);
            }
            if (mid < v) {
                if (!t[node].r) t[node].r = ++id;
                modify(t[node].r, mid + 1, r, u, v);
            }
            t[node].val = t[t[node].l].val + t[t[node].r].val;
        }
    }

    int get(int node, int l, int r, int u, int v) {
        if (t[node].val == r - l + 1) return min(r, v) - max(u, l) + 1;
        if (u <= l && r <= v) return t[node].val;
        int mid = (l + r) >> 1, sum = 0;
        if (u <= mid) {
            if (!t[node].l) t[node].l = ++ id;
            sum += get(t[node].l, l, mid, u, v);
        }
        if (mid < v) {
            if (!t[node].r) t[node].r = ++id;
            sum += get(t[node].r, mid + 1, r, u, v);
        }
        return sum;
    }

    void modify(int l, int r) {
        modify(1, 1, n, l, r);
    }

    int get(int l, int r) {
        return get(1, 1, n, l, r);
    }
};

void solve(void) {
    int q, ans = 0; cin >> q;
    segment_tree st((int) INF);

    while (q --) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            ans = st.get(l + ans, r + ans);
            cout << ans << '\n';
        } else {
            st.modify(l + ans, r + ans);
        }
    }
}

int main(void) {
    cin.tie(0)->sync_with_stdio(0); 
    int test = 1;
    // cin >> test;
    while (test --) {
        solve();
    }
    return 0;
}

• Subtask 1: 100 / 100