Submission #1290067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290067		abdualrimali	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	0 ms	332 KiB

apple

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Node {
    ll val, lazy;
    int left, right;
    bool is_lazy;
    Node(ll v = 0) : val(v), lazy(0), left(-1), right(-1), is_lazy(false) {}
    static Node identity() { return Node(0); }
    static Node merge(const Node &a, const Node &b) {
        Node ret;
        ret.val = a.val + b.val;
        return ret;
    }
    void apply(ll x, int l, int r) {
        val += x * (r - l + 1); // range add
        lazy += x;
        is_lazy = true;
    }
    void reset() {
        lazy = 0;
        is_lazy = false;
    }
};

struct SparseSegmentTree {
#define L tree[node].left
#define R tree[node].right
#define MID ((l+r)>>1)
private:
    int sz, timer = 0;
    vector<Node> tree;

    void grow(int node) {
        if (L == -1) { L = ++timer; tree.push_back(Node()); }
        if (R == -1) { R = ++timer; tree.push_back(Node()); }
    }

    void propagate(int node, int l, int r) {
        if (!tree[node].is_lazy || l == r) return;
        grow(node);
        tree[L].apply(tree[node].lazy, l, MID);
        tree[R].apply(tree[node].lazy, MID+1, r);
        tree[node].reset();
    }

    void update(int l, int r, int node, int lq, int rq, ll val) {
        propagate(node, l, r);
        if (l > rq || r < lq) return;
        if (lq <= l && r <= rq) {
            tree[node].apply(val, l, r);
            return;
        }
        grow(node);
        update(l, MID, L, lq, rq, val);
        update(MID+1, r, R, lq, rq, val);
        tree[node] = Node::merge(tree[L], tree[R]);
    }

    ll query(int l, int r, int node, int lq, int rq) {
        propagate(node, l, r);
        if (l > rq || r < lq) return 0;
        if (lq <= l && r <= rq) return tree[node].val;
        grow(node);
        return query(l, MID, L, lq, rq) + query(MID+1, r, R, lq, rq);
    }

public:
    SparseSegmentTree(int n, int q = 0) : sz(n) {
        if (q > 0) tree.reserve(2 * q * __lg(n));
        tree.push_back(Node());
    }

    void update(int lq, int rq, ll val) { update(0, sz-1, 0, lq, rq, val); }
    ll query(int lq, int rq) { return query(0, sz-1, 0, lq, rq); }

#undef L
#undef R
#undef MID
};

int main() {
    int query_num;
    cin >> query_num;
    const int RANGE_SIZE = 1e9;
    SparseSegmentTree st(RANGE_SIZE + 1, query_num);

    int c = 0;
    for (int i = 0; i < query_num; i++) {
        int type, x, y;
        cin >> type >> x >> y;
        if (type == 1) {
            c = st.query(x + c, y + c);
            cout << c << '\n';
        } else if (type == 2) {
            st.update(x + c, y + c, 1);
        }
    }
}

• Subtask 1: 0 / 100