제출 #1205774

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1205774		GoBananas69	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	544 ms	266112 KiB

apple

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

struct node {
    node *x = nullptr, *y = nullptr;
    ll L, R, m;
    ll sum = 0;
    bool has = false;
    void init(ll l, ll r) { L = l, R = r, m = (L + R) / 2; }
    node(ll l, ll r) {
        // cout << "Created" << ' ' << l << ' ' << r << '\n';
        init(l, r);
        x = y = nullptr;
        has = false;
        sum = 0;
    }
    void push() {
        if (L == R || !has) return;
        if (x == nullptr) x = new node(L, m);
        if (y == nullptr) y = new node(m + 1, R);
        x->sum = m - L + 1;
        y->sum = R - m;
        x->has = y->has = true;
        has = false;
    }
    void update(ll l, ll r) {
        if (l > R || L > r) return;
        if (L == l && r == R) {
            sum = R - L + 1;
            has = true;
            return;
        }
        push();
        if (r <= m) {
            if (x == nullptr) x = new node(L, m);
            x->update(l, r);
            sum = x->sum + (y != nullptr ? y->sum : 0);
        } else if (l > m) {
            if (y == nullptr) y = new node(m + 1, R);
            y->update(l, r);
            sum = y->sum + (x != nullptr ? x->sum : 0);
        } else {
            if (x == nullptr) x = new node(L, m);
            if (y == nullptr) y = new node(m + 1, R);
            x->update(l, m);
            y->update(m + 1, r);
            sum = x->sum + y->sum;
        }
    }
    ll query(ll l, ll r) {
        if (l > R || L > r) return 0;
        if (L == l && r == R) {
            // cout << "sum: " << l << ' ' << r << ": " << sum << '\n';
            return sum;
        }
        push();
        ll res = 0;
        if (r <= m) {
            if (x != nullptr) res += x->query(l, r);
        } else if (l > m) {
            if (y != nullptr) res += y->query(l, r);
        } else {
            if (x != nullptr) res += x->query(l, m);
            if (y != nullptr) res += y->query(m + 1, r);
        }
        return res;
    }
    ~node() {
        delete x;
        delete y;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int m;
    cin >> m;
    ll c = 0;
    const ll n = 1e9 + 7;
    node *root = new node(1, n);
    while (m--) {
        int type;
        ll l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            l += c;
            r += c;
            c = root->query(l, r);
            cout << c << '\n';
        } else {
            l += c;
            r += c;
            root->update(l, r);
        }
    }
    delete root;
    return 0;
}

• Subtask 1: 0 / 100