Submission #451950

#	Time	Username	Problem	Language	Result	Execution time	Memory
451950		ilmar	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	568 ms	207772 KiB

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 / 100