Submission #465408

#	Time	Username	Problem	Language	Result	Execution time	Memory
465408		Pommes	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	513 ms	262148 KiB

apple

#include <bits/stdc++.h>
#define endl        '\n'
using namespace std;
 
 
struct SegmentTree {
private:
    int acc, lazy;
    SegmentTree* left_child, * right_child;
    int tl, tr; // left and right endpoint of segment (inclusive)
public:
    SegmentTree(int left, int right) {
        left_child = right_child = nullptr;
        tl = left;
        tr = right;
        acc = 0;
        lazy = 0;
    }
    SegmentTree(vector<int>& a) {
        tl = 0; tr = (int)a.size() - 1;
        for (int i = 0; i <= tr; ++i) {
            point_update(i, a[i]);
        }
    }
    int merge_function(int a, int b) {
        return a + b;
    }
    void merge() {
        int tm = tl + (tr - tl) / 2;
        acc = merge_function(
            left_child->query(tl, tm),
            right_child->query(tm + 1, tr)
        );
    }
    void point_update(int position, int value) {
        push();
        if (tl == tr) {
            acc = value;
        } else {
            int tm = tl + (tr - tl) / 2;
            if (position <= tm)
                left_child->point_update(position, value);
            else
                right_child->point_update(position, value);
            merge();
        }
    }
    void update(int l, int r) {
        push();
        if (l == tl && tr == r) {
            lazy = 1;
        } else {
            int tm = tl + (tr - tl) / 2;
            if (r <= tm) left_child->update(l, r);
            else if (l > tm) right_child->update(l, r);
            else {
                left_child->update(l, tm);
                right_child->update(tm + 1, r);
            }
            merge();
        }
    }
    int query(int l, int r) {
        push();
        if (l == tl && tr == r) return acc;
        int tm = tl + (tr - tl) / 2;
        if (r <= tm) return left_child->query(l, r);
        if (l > tm) return right_child->query(l, r);
        return merge_function(
            left_child->query(l, tm),
            right_child->query(tm + 1, r)
        );
    }
    void push() {
        construct_children();
        if (lazy) {
            acc = tr - (tl - 1);
            if (tl < tr) {
                left_child->lazy = lazy;
                right_child->lazy = lazy;
            }
            lazy = 0;
        }
    }
    void construct_children() {
        if (tl == tr) return;
        int tm = tl + (tr - tl) / 2;
        if (!left_child) left_child = new SegmentTree(tl, tm);
        if (!right_child) right_child = new SegmentTree(tm + 1, tr);
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    SegmentTree tree(1, (int)1e9);
    int M;
    cin >> M;
    int C = 0;
    while (M--) {
        int D, X, Y;
        cin >> D >> X >> Y;
        if (D == 1) {
            C = tree.query(X + C, Y + C);
            cout << C << endl;
        } else {
            tree.update(X + C, Y + C);
        }
    }
    return 0;
}

• Subtask 1: 0 / 100