답안 #472803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
472803	2021-09-14T11:00:13 Z	zxcvbnm	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	19 ms	6348 KB

apple

#include <bits/stdc++.h>
using namespace std;
constexpr int nax = 1<<30;
struct Node {
    int sum, l, r;
    bool on;
    Node *left, *right;
    Node(int le, int ri) : sum(0), l(le), r(ri), on(false), left(nullptr), right(nullptr) {};
};

bool out(int l, int r, int L, int R) {
    return L >= r || l >= R;
}

struct St {
    Node* root;
    St() {
        root = new Node(0, nax);
    }

    void apply(Node* curr) {
        if (curr->on) {
            curr->sum = (curr->r - curr->l);

            int mid = (curr->l + curr->r) / 2;
            if (!curr->left) {
                curr->left = new Node(curr->l, mid);
            }

            curr->left->on = true;
            curr->left->sum = (mid - curr->l);

            if (!curr->right) {
                curr->right = new Node(mid, curr->r);
            }

            curr->right->on = true;
            curr->left->sum = (curr->r - mid);

            curr->on = false;
        }
    }

    void set(int L, int R) {
        set_r(root, L, R);
    }

    void set_r(Node* curr, int L, int R) {
        if (curr->l >= L && R >= curr->r) {
            curr->on = true;
            curr->sum = (curr->r - curr->l);
            return;
        }

        apply(curr);
        int mid = (curr->l + curr->r) / 2;

        // [l, mid)
        if (!out(curr->l, mid, L, R)) {
            if (!curr->left) {
                curr->left = new Node(curr->l, mid);
            }
            set_r(curr->left, L, R);
        }

        // [mid, r)
        if (!out(mid, curr->r, L, R)) {
            if (!curr->right) {
                curr->right = new Node(mid, curr->r);
            }
            set_r(curr->right, L, R);
        }

        int s = 0;
        if (curr->left) {
            s += curr->left->sum;
        }
        if (curr->right) {
            s += curr->right->sum;
        }

        curr->sum = s;
    }

    int sum(int L, int R) {
        return sum_r(root, L, R);
    }

    int sum_r(Node* curr, int L, int R) {
        if (curr == nullptr || L >= curr->r || curr->l >= R) return 0;

        apply(curr);

        if (curr->l >= L && R >= curr->r) {
            return curr->sum;
        }

        return sum_r(curr->left, L, R) + sum_r(curr->right, L, R);
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    St st;
    int q;
    cin >> q;

    int c = 0;
    while(q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            cin >> l >> r;
            l += c, r += c;
            int s = st.sum(l, r+1);
            c = s;
            cout << s << "\n";
        }
        else {
            int l, r;
            cin >> l >> r;
            l += c, r += c;
            st.set(l, r+1);
        }
    }
    return 0;
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Incorrect	19 ms	6348 KB	Output isn't correct
5	Halted	0 ms	0 KB	-