Submission #472820

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
472820	2021-09-14T11:26:09 Z	zxcvbnm	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	578 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) {
            curr->sum = (curr->r - curr->l);

            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	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	16 ms	6092 KB	Output is correct
5	Correct	26 ms	7636 KB	Output is correct
6	Correct	20 ms	7296 KB	Output is correct
7	Correct	21 ms	7628 KB	Output is correct
8	Correct	162 ms	57408 KB	Output is correct
9	Correct	379 ms	97024 KB	Output is correct
10	Correct	344 ms	109816 KB	Output is correct
11	Correct	361 ms	117932 KB	Output is correct
12	Correct	367 ms	121320 KB	Output is correct
13	Correct	332 ms	139368 KB	Output is correct
14	Correct	336 ms	140344 KB	Output is correct
15	Correct	550 ms	255872 KB	Output is correct
16	Correct	556 ms	257784 KB	Output is correct
17	Correct	347 ms	144652 KB	Output is correct
18	Correct	352 ms	145048 KB	Output is correct
19	Correct	560 ms	262144 KB	Output is correct
20	Correct	578 ms	262144 KB	Output is correct