Submission #465404

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
465404	2021-08-15T21:25:20 Z	Pommes	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	611 ms	262148 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	32 ms	7700 KB	Output is correct
5	Correct	34 ms	9188 KB	Output is correct
6	Correct	34 ms	8916 KB	Output is correct
7	Correct	41 ms	9192 KB	Output is correct
8	Correct	239 ms	69280 KB	Output is correct
9	Correct	521 ms	118404 KB	Output is correct
10	Correct	539 ms	132548 KB	Output is correct
11	Correct	578 ms	143484 KB	Output is correct
12	Correct	524 ms	148256 KB	Output is correct
13	Correct	508 ms	181128 KB	Output is correct
14	Correct	519 ms	183448 KB	Output is correct
15	Runtime error	611 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-