Submission #470800

#	Time	Username	Problem	Language	Result	Execution time	Memory
470800		zxcvbnm	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	249 ms	262148 KiB

apple

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int nax = 1<<30;
struct Node {
    int sum, l, r;
    bool lazy;
    int left, right;
    Node(int le, int ri) : sum(0), l(le), r(ri), lazy(false), left(-1), right(-1) {};
};
struct St {
    vector<Node> tree;
    St() {
        tree.emplace_back(Node(0, nax));
    }

    void modify(int idx) {
        if (tree[idx].lazy) {
            int mid = (tree[idx].l + tree[idx].r) / 2;
            // left
            if (tree[idx].left == -1) {
                tree[idx].left = tree.size();
                tree.emplace_back(Node(tree[idx].l, mid));
            }
            tree[tree[idx].left].sum = (mid-tree[idx].l);
            tree[tree[idx].left].lazy = true;

            // right
            if (tree[idx].right == -1) {
                tree[idx].right = tree.size();
                tree.emplace_back(Node(mid, tree[idx].r));
            }
            tree[tree[idx].right].sum = (mid-tree[idx].l);
            tree[tree[idx].right].lazy = true;

        }
    }

    void set(int L, int R) {
        set_r(0, L, R);
    }

    void set_r(int idx, int L, int R) {
        if (tree[idx].l >= R || L >= tree[idx].r) return;

        if (tree[idx].l >= L && R >= tree[idx].r) {
            tree[idx].lazy = true;
            tree[idx].sum = tree[idx].r - tree[idx].l;
            return;
        }

        modify(idx);
        int mid = (tree[idx].l + tree[idx].r) / 2;
        if (mid > L) {
            if (tree[idx].left == -1) {
                tree[idx].left = tree.size();
                tree.emplace_back(Node(tree[idx].l, mid));
            }
            set_r(tree[idx].left, L, R);
        }
        if (R > mid) {
            if (tree[idx].right == -1) {
                tree[idx].right = tree.size();
                tree.emplace_back(Node(mid, tree[idx].r));
            }
            set_r(tree[idx].right, L, R);
        }

        int s1 = 0, s2 = 0;
        if (tree[idx].left != -1) {
            s1 += tree[tree[idx].left].sum;
        }
        if (tree[idx].right != -1) {
            s2 += tree[tree[idx].right].sum;
        }

        tree[idx].sum = s1 + s2;
    }

    int sum(int L, int R) {
        return sum_r(0, L, R);
    }

    int sum_r(int idx, int L, int R) {

        if (tree[idx].l >= R || L >= tree[idx].r) return 0;
        if (tree[idx].l >= L && R >= tree[idx].r) {
            return tree[idx].sum;
        }

        modify(idx);
        int s1 = sum_r(tree[idx].left, L, R);
        int s2 = sum_r(tree[idx].right, L, R);

        return s1 + s2;
    }

//    void traverse() {
//        traverse(root);
//    }
//
//    void traverse(Node* curr) {
//        if (curr == nullptr) return;
//        cout << tree[idx].sum << " [" << tree[idx].l << ", " << tree[idx].r << "]\n";
//        traverse(tree[idx].left);
//        traverse(tree[idx].right);
//    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    St st;

    int c = 0;
    while(q--) {
        int type;
        cin >> type;
        int l, r;
        cin >> l >> r;
        l += c, r += c;
        if (type == 1) {
//            st.traverse();
            int s = st.sum(l, r+1);
            c = s;
            cout << s << "\n";
        }
        else {
            st.set(l, r+1);
        }
    }
}

• Subtask 1: 0 / 100