Submission #667463

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
667463	2022-12-01T12:08:08 Z	bojackduy	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	77 ms	150604 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 (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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	77 ms	150604 KB	Output isn't correct
2	Halted	0 ms	0 KB	-