Submission #472822

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
472822	2021-09-14T11:28:15 Z	zxcvbnm	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	470 ms	207848 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;

        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.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	1 ms	204 KB	Output is correct
4	Correct	15 ms	4940 KB	Output is correct
5	Correct	20 ms	5880 KB	Output is correct
6	Correct	22 ms	5752 KB	Output is correct
7	Correct	19 ms	5988 KB	Output is correct
8	Correct	135 ms	44272 KB	Output is correct
9	Correct	295 ms	75164 KB	Output is correct
10	Correct	309 ms	84804 KB	Output is correct
11	Correct	307 ms	91336 KB	Output is correct
12	Correct	306 ms	94024 KB	Output is correct
13	Correct	307 ms	108800 KB	Output is correct
14	Correct	271 ms	109872 KB	Output is correct
15	Correct	446 ms	201360 KB	Output is correct
16	Correct	435 ms	202820 KB	Output is correct
17	Correct	277 ms	113476 KB	Output is correct
18	Correct	284 ms	113636 KB	Output is correct
19	Correct	459 ms	207848 KB	Output is correct
20	Correct	470 ms	207524 KB	Output is correct