Submission #465409

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
465409	2021-08-15T22:53:32 Z	Pommes	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	350 ms	163776 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) {
        if (lazy || acc == tr - tl + 1)
            return r - l + 1;
        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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	13 ms	4044 KB	Output is correct
5	Correct	16 ms	4856 KB	Output is correct
6	Correct	17 ms	4884 KB	Output is correct
7	Correct	16 ms	4864 KB	Output is correct
8	Correct	115 ms	37124 KB	Output is correct
9	Correct	226 ms	65632 KB	Output is correct
10	Correct	235 ms	72176 KB	Output is correct
11	Correct	262 ms	76868 KB	Output is correct
12	Correct	247 ms	79044 KB	Output is correct
13	Correct	241 ms	85108 KB	Output is correct
14	Correct	264 ms	87200 KB	Output is correct
15	Correct	341 ms	159972 KB	Output is correct
16	Correct	344 ms	160520 KB	Output is correct
17	Correct	231 ms	90188 KB	Output is correct
18	Correct	258 ms	89924 KB	Output is correct
19	Correct	350 ms	163584 KB	Output is correct
20	Correct	342 ms	163776 KB	Output is correct