Submission #465408

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
465408	2021-08-15T22:41:21 Z	Pommes	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	513 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	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	19 ms	7596 KB	Output is correct
5	Correct	26 ms	9280 KB	Output is correct
6	Correct	25 ms	8956 KB	Output is correct
7	Correct	30 ms	9264 KB	Output is correct
8	Correct	200 ms	69316 KB	Output is correct
9	Correct	445 ms	118584 KB	Output is correct
10	Correct	422 ms	132612 KB	Output is correct
11	Correct	454 ms	143576 KB	Output is correct
12	Correct	451 ms	148380 KB	Output is correct
13	Correct	408 ms	181188 KB	Output is correct
14	Correct	414 ms	183400 KB	Output is correct
15	Runtime error	513 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-