제출 #1205095

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1205095		GoBananas69	원숭이와 사과 나무 (IZhO12_apple)	C++20	100 / 100	440 ms	205588 KiB

apple

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

struct Node {
    Node *l = nullptr, *r = nullptr;
    ll sum = 0;
    bool covered = false;

    Node() = default;

    void push(ll L, ll R) {
        if (!covered || L == R) return;
        ll M = (L + R) >> 1;
        if (!l) l = new Node();
        if (!r) r = new Node();
        l->covered = true;
        l->sum = (M - L + 1);
        r->covered = true;
        r->sum = (R - M);
        covered = false;
    }

    void update(ll L, ll R, ll ql, ll qr) {
        if (qr < L || R < ql) return;
        if (ql <= L && R <= qr) {
            covered = true;
            sum = (R - L + 1);
            return;
        }
        push(L, R);
        ll M = (L + R) >> 1;
        if (!l) l = new Node();
        if (!r) r = new Node();
        l->update(L, M, ql, qr);
        r->update(M + 1, R, ql, qr);
        sum = l->sum + r->sum;
    }

    ll query(ll L, ll R, ll ql, ll qr) {
        if (qr < L || R < ql) return 0;
        if (ql <= L && R <= qr) return sum;
        push(L, R);
        ll M = (L + R) >> 1;
        ll ans = 0;
        if (l) ans += l->query(L, M, ql, qr);
        if (r) ans += r->query(M + 1, R, ql, qr);
        return ans;
    }

    ~Node() {
        delete l;
        delete r;
    }
};

int main() {
    cin.tie(0) -> sync_with_stdio(0);

    int M;
    cin >> M;

    const ll N = 1'000'000'007;
    Node *root = new Node();

    ll C = 0;
    while (M--) {
        int D;
        ll X, Y;
        cin >> D >> X >> Y;
        X += C;
        Y += C;
        if (X > Y) swap(X, Y);

        if (D == 2) {
            root->update(1, N, X, Y);
        } else {
            C = root->query(1, N, X, Y);
            cout << C << "\n";
        }
    }

    delete root;
    return 0;
}

• Subtask 1: 100 / 100