Submission #1253567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253567		Balsa	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	126 ms	262844 KiB

apple

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

using ll = int;

struct segtree {
    ll size = 1;
    vector<ll> sums, opr;
    const ll NEUTRAL_ELEMENT = 0;
    const ll NO_OPERATION = 0;

    segtree(ll n) {
        while (size < n) size*=2;
        sums.assign(2*size, NEUTRAL_ELEMENT);
        opr.assign(2*size, NO_OPERATION);
    }

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

        opr[2*x+1] = opr[2*x+2] = opr[x];
        sums[2*x+1] = sums[2*x+2] = (rx-lx)/2 * opr[x];

        opr[x] = NO_OPERATION;
    }

    void set(ll l, ll r, ll v, ll x, ll lx, ll rx) {
        prop(x, lx, rx);
        if (rx <= l || lx >= r) return;
        if (lx >= l && rx <= r) {
            opr[x] = v;
            sums[x] = (rx-lx)*v;
            return;
        }

        ll m = (lx+rx)/2;
        set(l, r, v, 2*x+1, lx, m);
        set(l, r, v, 2*x+2, m, rx);

        sums[x] = sums[2*x+1] + sums[2*x+2];
    }

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

    ll query(ll l, ll r, ll x, ll lx, ll rx) {
        prop(x, lx, rx);
        if (rx <= l || lx >= r) return NEUTRAL_ELEMENT;
        if (lx >= l && rx <= r) return sums[x];

        ll m = (lx+rx)/2;
        return query(l, r, 2*x+1, lx, m) + query(l, r, 2*x+2, m, rx);
    }

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

void solve() {
    segtree st(1e7);
    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 {
            ll cnt = st.query(l + c, r + c);
            c = cnt;
            cout << cnt << '\n';
        }
    }
}

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

• Subtask 1: 0 / 100