Submission #477488

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
477488	2021-10-02T09:31:45 Z	Shin	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	126 ms	153328 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	76 ms	150580 KB	Output is correct
2	Correct	74 ms	150532 KB	Output is correct
3	Correct	72 ms	150596 KB	Output is correct
4	Correct	82 ms	150668 KB	Output is correct
5	Correct	74 ms	150712 KB	Output is correct
6	Correct	81 ms	150748 KB	Output is correct
7	Correct	80 ms	150768 KB	Output is correct
8	Correct	89 ms	151588 KB	Output is correct
9	Correct	108 ms	152732 KB	Output is correct
10	Correct	126 ms	152724 KB	Output is correct
11	Correct	103 ms	152776 KB	Output is correct
12	Correct	122 ms	152740 KB	Output is correct
13	Correct	119 ms	153068 KB	Output is correct
14	Correct	125 ms	153152 KB	Output is correct
15	Correct	103 ms	153160 KB	Output is correct
16	Correct	113 ms	153328 KB	Output is correct
17	Correct	124 ms	153172 KB	Output is correct
18	Correct	113 ms	153156 KB	Output is correct
19	Correct	118 ms	153160 KB	Output is correct
20	Correct	104 ms	153160 KB	Output is correct