답안 #470785

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
470785	2021-09-05T15:15:23 Z	zxcvbnm	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	598 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 (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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 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	28 ms	8344 KB	Output is correct
5	Correct	27 ms	10264 KB	Output is correct
6	Correct	26 ms	9848 KB	Output is correct
7	Correct	27 ms	10188 KB	Output is correct
8	Correct	223 ms	78120 KB	Output is correct
9	Correct	424 ms	132624 KB	Output is correct
10	Correct	467 ms	150228 KB	Output is correct
11	Correct	505 ms	161376 KB	Output is correct
12	Correct	470 ms	166212 KB	Output is correct
13	Correct	443 ms	190704 KB	Output is correct
14	Correct	449 ms	193180 KB	Output is correct
15	Runtime error	598 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-