Submission #470782

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
470782	2021-09-05T15:09:24 Z	zxcvbnm	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	539 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 == 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;
        }
    }

    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 (curr->left == nullptr) {
            curr->left = new Node(curr->l, mid);
        }
        if (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 = curr->left->sum;
        int 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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	22 ms	8524 KB	Output is correct
5	Correct	26 ms	10308 KB	Output is correct
6	Correct	27 ms	9992 KB	Output is correct
7	Correct	26 ms	10352 KB	Output is correct
8	Correct	216 ms	78988 KB	Output is correct
9	Correct	433 ms	134360 KB	Output is correct
10	Correct	466 ms	152132 KB	Output is correct
11	Correct	473 ms	163140 KB	Output is correct
12	Correct	476 ms	168260 KB	Output is correct
13	Correct	440 ms	192748 KB	Output is correct
14	Correct	445 ms	195032 KB	Output is correct
15	Runtime error	539 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-