Submission #470790

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

            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 == 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 (mid >= L && curr->left == nullptr) {
            curr->left = new Node(curr->l, mid);
        }
        if (R >= mid && 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 = 0, s2 = 0;
        if (curr->left) {
            s1 += curr->left->sum;
        }
        if (curr->right) {
            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	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	27 ms	8456 KB	Output is correct
5	Correct	26 ms	10232 KB	Output is correct
6	Correct	26 ms	9892 KB	Output is correct
7	Correct	28 ms	10148 KB	Output is correct
8	Correct	253 ms	78224 KB	Output is correct
9	Correct	424 ms	132544 KB	Output is correct
10	Correct	541 ms	150212 KB	Output is correct
11	Correct	522 ms	161400 KB	Output is correct
12	Correct	470 ms	166272 KB	Output is correct
13	Correct	559 ms	190696 KB	Output is correct
14	Correct	485 ms	192964 KB	Output is correct
15	Runtime error	566 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-