Submission #470792

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
470792	2021-09-05T15:39:07 Z	zxcvbnm	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	557 ms	262148 KB

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->lazy) {
            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->l >= R || L >= curr->r) return;
        if (curr->l >= L && R >= curr->r) {
            curr->lazy = true;
            curr->sum = curr->r - curr->l;
            return;
        }

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

        int s1 = 0, s2 = 0;
        if (curr->left != nullptr) {
            s1 += curr->left->sum;
        }
        if (curr->right != nullptr) {
            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;
        if (curr->l >= L && R >= curr->r) {
            return curr->sum;
        }

        modify(curr);
        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.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	0 ms	204 KB	Output is correct
4	Correct	17 ms	6348 KB	Output is correct
5	Correct	21 ms	7556 KB	Output is correct
6	Correct	22 ms	7428 KB	Output is correct
7	Correct	21 ms	7632 KB	Output is correct
8	Correct	173 ms	58568 KB	Output is correct
9	Correct	333 ms	99736 KB	Output is correct
10	Correct	346 ms	112780 KB	Output is correct
11	Correct	413 ms	120632 KB	Output is correct
12	Correct	365 ms	124216 KB	Output is correct
13	Correct	329 ms	138992 KB	Output is correct
14	Correct	334 ms	140708 KB	Output is correct
15	Correct	557 ms	260580 KB	Output is correct
16	Correct	541 ms	262144 KB	Output is correct
17	Correct	353 ms	147400 KB	Output is correct
18	Correct	340 ms	147704 KB	Output is correct
19	Runtime error	547 ms	262148 KB	Execution killed with signal 9
20	Halted	0 ms	0 KB	-