Submission #1064765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064765		MrNanama	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	49 ms	157008 KiB

apple

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second

using namespace std;
using ll = long long;
const ll MAX_N = (1e9 + 5);
const ll MAX_CONST = (5e6);

template <typename T> ostream& operator<<(ostream& os, const vector<T>& vec){for (auto itr : vec){os << itr << " ";} return os;}

ll m;
ll c;
ll last_node;
ll seg;
vector<ll> val;
vector<ll> left_node;
vector<ll> right_node;
vector<ll> lazy;

void extend(ll ind, ll l, ll r) {
    if (l == r) { return; }

    if (left_node[ind] == -1) {
        left_node[ind] = ++last_node;
    }

    if (right_node[ind] == -1) {
        right_node[ind] = ++last_node;
    }
}

void pushdownwards(ll ind, ll l, ll r) {
    if (lazy[ind] == 0) { return; }

    extend(ind, l, r);
    val[ind] = (r - l + 1); // Segment is fully updated

    if (l != r) { // Not a leaf node
        lazy[left_node[ind]] = 1;
        lazy[right_node[ind]] = 1;
    }

    lazy[ind] = 0; // Clear the lazy flag
}

ll get_val(ll ind, ll tl, ll tr, ll l, ll r) {
    if (max<ll>(tl, l) > min<ll>(tr, r)) { return 0; } // No overlap

    pushdownwards(ind, l, r);

    if (tl <= l && r <= tr) { // Total overlap
        return val[ind];
    }

    extend(ind, l, r);
    ll m = l + (r - l) / 2;

    return get_val(left_node[ind], tl, tr, l, m) + get_val(right_node[ind], tl, tr, m + 1, r);
}

void upd(ll ind, ll tl, ll tr, ll l, ll r) {
    pushdownwards(ind, l, r);

    if (max<ll>(tl, l) > min<ll>(tr, r)) { return; } // No overlap

    if (tl <= l && r <= tr) { // Total overlap
        lazy[ind] = 1;
        pushdownwards(ind, l, r);
        return;
    }

    extend(ind, l, r);
    ll m = l + (r - l) / 2;

    upd(left_node[ind], tl, tr, l, m);
    upd(right_node[ind], tl, tr, m + 1, r);

    val[ind] = val[left_node[ind]] + val[right_node[ind]];
}

void solve() {
    cin >> m;
    c = 0;
    last_node = 0;
    val.assign(MAX_CONST, 0);
    left_node.assign(MAX_CONST, -1);
    right_node.assign(MAX_CONST, -1);
    lazy.assign(MAX_CONST, 0);

    seg = ++last_node;

    for (ll i = 0; i < m; i++) {
        ll opr, l, r;
        cin >> opr >> l >> r;

        if (opr == 1) {
            ll res = get_val(seg, l + c, r + c, 0, MAX_N);
            c += res;
            cout << res << endl;
        } else {
            upd(seg, l + c, r + c, 0, MAX_N);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    solve();
}

• Subtask 1: 0 / 100