Submission #472821

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
472821	2021-09-14T11:26:33 Z	zxcvbnm	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	551 ms	262144 KB

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;

        apply(curr);

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

        return sum_r(curr->left, L, R) + sum_r(curr->right, L, R);
    }
};
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.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	17 ms	6208 KB	Output is correct
5	Correct	21 ms	7664 KB	Output is correct
6	Correct	21 ms	7332 KB	Output is correct
7	Correct	20 ms	7572 KB	Output is correct
8	Correct	171 ms	57020 KB	Output is correct
9	Correct	330 ms	95836 KB	Output is correct
10	Correct	352 ms	108488 KB	Output is correct
11	Correct	365 ms	116664 KB	Output is correct
12	Correct	372 ms	120192 KB	Output is correct
13	Correct	338 ms	137984 KB	Output is correct
14	Correct	328 ms	138844 KB	Output is correct
15	Correct	537 ms	253764 KB	Output is correct
16	Correct	551 ms	255688 KB	Output is correct
17	Correct	335 ms	142712 KB	Output is correct
18	Correct	337 ms	143016 KB	Output is correct
19	Correct	549 ms	262144 KB	Output is correct
20	Correct	548 ms	262144 KB	Output is correct