Submission #451950

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
451950	2021-08-03T13:54:04 Z	ilmar	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	568 ms	207772 KB

apple

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

class SegmentTree {
    public:
    struct Node {
        long long val;
        long long lzAdd;
        long long lzSet;

        struct Node *left, *right;
    };

    Node *root = new Node;

    SegmentTree() {
    }
    ~SegmentTree() {
    }

    void expand(Node *v) {
        if (v->left == NULL)
            v->left = new Node;
        if (v->right == NULL)
            v->right = new Node;
    }

    void push(Node *v, long long l, long long m, long long r) {
        expand(v);

        if (v->lzSet != 0) {
            v->left->lzSet = v->lzSet;
            v->right->lzSet = v->lzSet;

            v->left->val = v->lzSet * (m - l + 1);
            v->right->val = v->lzSet * (r - m);

            v->left->lzAdd = v->right->lzAdd = 0;

            v->lzSet = 0;
        }
        v->left->lzAdd += v->lzAdd;
        v->right->lzAdd += v->lzAdd;

        v->left->val += v->lzAdd * (m - l + 1);
        v->right->val += v->lzAdd * (r - m);

        v->lzAdd = 0;
    }

    long long sum(Node *v, long long tl, long long tr, long long l, long long r) {
        if (l > r)
            return 0;
        if (l == tl && r == tr)
            return v->val;
        long long tm = (tl + tr) / 2;
        push(v, tl, tm, tr);
        return sum(v->left, tl, tm, l, min(r, tm)) + sum(v->right, tm + 1, tr, max(l, tm + 1), r);
    }

    void update_add(Node *v, long long tl, long long tr, long long l, long long r, long long add) {
        if (l > r)
            return;

        if (l == tl && r == tr) {
            v->lzAdd += add;
            v->val += (tr - tl + 1) * add;
        } else {
            long long tm = (tl + tr) / 2;
            push(v, tl, tm, tr);
            update_add(v->left, tl, tm, l, min(tm, r), add);
            update_add(v->right, tm + 1, tr, max(l, tm + 1), r, add);
            v->val = v->left->val + v->right->val;
        }
    }

    void update_assign(Node *v, long long tl, long long tr, long long l, long long r, long long new_val) {
        if (l > r)
            return;
        if (l == tl && r == tr) {
            v->lzSet = new_val;
            v->lzAdd = 0;
            v->val = new_val * (tr - tl + 1);
        } else {
            long long tm = (tl + tr) / 2;
            push(v, tl, tm, tr);
            update_assign(v->left, tl, tm, l, min(tm, r), new_val);
            update_assign(v->right, tm + 1, tr, max(l, tm + 1), r, new_val);
            v->val = v->left->val + v->right->val;
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int m;
    const int n = 1e9;
    cin >> m;

    SegmentTree st = SegmentTree();

    int c = 0;

    while (m--) {
        int d, x, y;
        cin >> d >> x >> y;
        x--, y--;
        x += c;
        y += c;
        if (d == 1) {
            int red = st.sum(st.root, 0, n - 1, x, y);
            cout << red << endl;
            c = red;
        } else {
            st.update_assign(st.root, 0, n - 1, x, y, 1);
        }
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	22 ms	4924 KB	Output is correct
5	Correct	27 ms	5928 KB	Output is correct
6	Correct	26 ms	5736 KB	Output is correct
7	Correct	27 ms	5964 KB	Output is correct
8	Correct	198 ms	44704 KB	Output is correct
9	Correct	368 ms	77260 KB	Output is correct
10	Correct	403 ms	85460 KB	Output is correct
11	Correct	397 ms	91632 KB	Output is correct
12	Correct	410 ms	94476 KB	Output is correct
13	Correct	377 ms	109960 KB	Output is correct
14	Correct	375 ms	110972 KB	Output is correct
15	Correct	563 ms	201764 KB	Output is correct
16	Correct	552 ms	203196 KB	Output is correct
17	Correct	403 ms	114764 KB	Output is correct
18	Correct	385 ms	114768 KB	Output is correct
19	Correct	568 ms	207772 KB	Output is correct
20	Correct	552 ms	207676 KB	Output is correct