Submission #1253633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253633		Balsa	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	422 ms	254748 KiB

apple

#include <bits/stdc++.h>
using namespace std;

using ll = int;
const bool NO_OPERATION = 0;

struct segtree {
    struct node {
        ll sum = 0;
        bool opr = NO_OPERATION;
        node *left = nullptr, *right = nullptr;

        void extend(ll lx, ll rx) {
            if (left == nullptr && rx-lx > 1) {
                left = new node();
                right = new node();
            }
        }

        void prop(ll lx, ll rx) {
            if (rx-lx == 1) return;
            if (opr == NO_OPERATION) return;

            left->opr = right->opr = opr;
            left->sum = right->sum = (rx-lx)/2 * opr;

            opr = NO_OPERATION;
        }

        void set(ll l, ll r, ll v, ll lx, ll rx) {
            extend(lx, rx);
            prop(lx, rx);
            if (rx <= l || lx >= r) return;
            if (lx >= l && rx <= r) {
                opr = 1;
                sum = (rx-lx);
                return;
            }

            ll m = (lx+rx)/2;
            left->set(l, r, v, lx, m);
            right->set(l, r, v, m, rx);

            sum = left->sum + right->sum;
        }

        ll query(ll l, ll r, ll lx, ll rx) {
            extend(lx, rx);
            prop(lx, rx);
            if (rx <= l || lx >= r) return 0;
            if (lx >= l && rx <= r) return sum;

            ll m = (lx+rx)/2;
            return left->query(l, r, lx, m) + right->query(l, r, m, rx);
        }
    };

    ll size = 1;
    node* root = new node();

    segtree(ll n) {
        while (size < n) size*=2;
    }

    void set(ll l, ll r, ll v) {
        root->set(l, r, v, 0, size);
    }

    ll query(ll l, ll r) {
        return root->query(l, r, 0, size);
    }
};

void solve() {
    segtree st(1e9);
    
    ll c = 0;
    ll m; cin >> m;
    for (ll q = 0; q < m; q++) {
        ll t, l, r;
        cin >> t >> l >> r;
        l--;
        if (t == 2) {
            st.set(l + c, r + c, 1);
        } else {
            c = st.query(l + c, r + c);
            cout << c << '\n';
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
}

• Subtask 1: 100 / 100