Submission #472822

#	Time	Username	Problem	Language	Result	Execution time	Memory
472822		zxcvbnm	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	470 ms	207848 KiB

apple

#include <bits/stdc++.h>
using namespace std;
constexpr int nax = 1<<30;
struct Node {
    int sum, l, r;
    bool on;
    Node *left, *right;
    Node(int le, int ri) : sum(0), l(le), r(ri), on(false), left(nullptr), right(nullptr) {};
};

bool out(int l, int r, int L, int R) {
    return L >= r || l >= R;
}

struct St {
    Node* root;
    St() {
        root = new Node(0, nax);
    }

    void apply(Node* curr) {
        if (curr->on) {
            int mid = (curr->l + curr->r) / 2;
            if (!curr->left) {
                curr->left = new Node(curr->l, mid);
            }

            curr->left->on = true;
            curr->left->sum = (mid - curr->l);

            if (!curr->right) {
                curr->right = new Node(mid, curr->r);
            }

            curr->right->on = true;
            curr->right->sum = (curr->r - mid);

            curr->on = false;
        }
    }

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

    void set_r(Node* curr, int L, int R) {
        if (curr->l >= L && R >= curr->r) {
            curr->on = true;
            curr->sum = (curr->r - curr->l);
            return;
        }

        apply(curr);
        int mid = (curr->l + curr->r) / 2;

        // [l, mid)
        if (!out(curr->l, mid, L, R)) {
            if (!curr->left) {
                curr->left = new Node(curr->l, mid);
            }
            set_r(curr->left, L, R);
        }

        // [mid, r)
        if (!out(mid, curr->r, L, R)) {
            if (!curr->right) {
                curr->right = new Node(mid, curr->r);
            }
            set_r(curr->right, L, R);
        }

        int s = 0;
        if (curr->left) {
            s += curr->left->sum;
        }
        if (curr->right) {
            s += curr->right->sum;
        }

        curr->sum = s;
    }

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

    int sum_r(Node* curr, int L, int R) {
        if (!curr || L >= curr->r || curr->l >= R) return 0;

        if (curr->l >= L && R >= curr->r) {
            return curr->sum;
        }

        apply(curr);

        int s = 0;
        if (curr->left) {
            s += sum_r(curr->left, L, R);
        }
        if (curr->right) {
            s += sum_r(curr->right, L, R);
        }

        return s;
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    St st;
    int q;
    cin >> q;

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

• Subtask 1: 100 / 100