Submission #470790

#	Time	Username	Problem	Language	Result	Execution time	Memory
470790		zxcvbnm	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	566 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;
    Node *left, *right;
    Node(int le, int ri) : sum(0), l(le), r(ri), lazy(false), left(nullptr), right(nullptr) {};
};
struct St {
    Node* root;
    St() {
        root = new Node(0, nax);
    }

    void modify(Node* curr) {
        if (curr == nullptr) return;

        if (curr->lazy) {
            curr->sum = (curr->r - curr->l);
            int mid = (curr->l + curr->r) / 2;
            // left
            if (curr->left == nullptr) {
                curr->left = new Node(curr->l, mid);
            }
            curr->left->sum = (mid-curr->l);
            curr->left->lazy = true;

            // right
            if (curr->right == nullptr) {
                curr->right = new Node(mid, curr->r);
            }
            curr->right->sum = (curr->r-mid);
            curr->right->lazy = true;

            curr->lazy = false;
        }
    }

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

    void set_r(Node* curr, int L, int R) {
        if (curr == nullptr) return;

//        cout << curr->l << " " << curr->r << "\n";
        if (curr->l >= R || L >= curr->r) return;
        if (curr->l >= L && R >= curr->r) {
            curr->lazy = true;
            return;
        }

        modify(curr);
        int mid = (curr->l + curr->r) / 2;
        if (mid >= L && curr->left == nullptr) {
            curr->left = new Node(curr->l, mid);
        }
        if (R >= mid && curr->right == nullptr) {
            curr->right = new Node(mid, curr->r);
        }

        set_r(curr->left, L, R);
        set_r(curr->right, L, R);
        modify(curr->left);
        modify(curr->right);

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

        curr->sum = s1 + s2;
    }

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

    int sum_r(Node* curr, int L, int R) {
        if (curr == nullptr) return 0;

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

        int s1 = sum_r(curr->left, L, R);
        int s2 = sum_r(curr->right, L, R);

        return s1 + s2;
    }

    void traverse() {
        traverse(root);
    }

    void traverse(Node* curr) {
        if (curr == nullptr) return;
        cout << curr->sum << " [" << curr->l << ", " << curr->r << "]\n";
        traverse(curr->left);
        traverse(curr->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