Submission #470795

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
470795	2021-09-05T15:46:24 Z	zxcvbnm	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	465 ms	207264 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->sum = (curr->r-curr->l);
            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);
        }
        if (R > mid) {
            if (curr->right == nullptr) curr->right = new Node(mid, curr->r);
            set_r(curr->right, L, R);
        }

        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

100.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	18 ms	4888 KB	Output is correct
5	Correct	20 ms	5912 KB	Output is correct
6	Correct	18 ms	5708 KB	Output is correct
7	Correct	18 ms	5876 KB	Output is correct
8	Correct	147 ms	44376 KB	Output is correct
9	Correct	292 ms	75268 KB	Output is correct
10	Correct	315 ms	84872 KB	Output is correct
11	Correct	336 ms	91220 KB	Output is correct
12	Correct	323 ms	94016 KB	Output is correct
13	Correct	271 ms	108768 KB	Output is correct
14	Correct	284 ms	109928 KB	Output is correct
15	Correct	457 ms	201212 KB	Output is correct
16	Correct	465 ms	202784 KB	Output is correct
17	Correct	289 ms	113476 KB	Output is correct
18	Correct	293 ms	113768 KB	Output is correct
19	Correct	447 ms	207264 KB	Output is correct
20	Correct	465 ms	207232 KB	Output is correct