Submission #1175568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175568		matus192	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	406 ms	265720 KiB

apple

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;

#define REP(i, a, b) for (ll i = (a); i < (b); i++)
#define FOR(i, x) for (auto &i : x)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LMAX LONG_LONG_MAX
#define LMIN LONG_LONG_MIN
#define MOD 1000000007
#define SIR 1000000009

struct Node {
    ll sz, val, l, r;
    bool cele;
    Node *lson, *rson;
    Node(ll vl, ll vr) {
        l = vl;
        r = vr;
        sz = r - l;
        lson = NULL;
        rson = NULL;
        val = 0;
        cele = false;
    }

    void upd() {
        if (sz == 1) return;
        if (!lson) lson = new Node(l, (l + r) / 2);
        if (!rson) rson = new Node((l + r) / 2, r);
    }

    void remove() {
        if (sz == 1 || !cele) return;
        lson->cele = true;
        rson->cele = true;
        lson->val = lson->sz;
        rson->val = rson->sz;
    }

    ll sum(ll vl, ll vr) {
        if (vr <= l || vl >= r) return 0;
        if (vl <= l && vr >= r) return val;
        upd();
        remove();
        ll lans = lson->sum(vl, vr);
        ll rans = rson->sum(vl, vr);
        return lans + rans;
    }

    void prepni(ll vl, ll vr) {
        if (vr <= l || vl >= r) return;
        if (vl <= l && vr >= r) {
            cele = true;
            val = sz;
            return;
        }
        upd();
        remove();
        lson->prepni(vl, vr);
        rson->prepni(vl, vr);
        val = lson->val + rson->val;
    }
};

int main() {
    ll m;
    cin >> m;
    Node R = Node(0, 1e9+1);
    ll C = 0;
    REP(i, 0, m) {
        ll t, x, y;
        cin >> t >> x >> y;
        if (t == 1) {
            C = R.sum(x + C, y + C + 1);
            cout << C << '\n';
        } else {
            R.prepni(x + C, y + C + 1);
        }
    }

    return 0;
}

• Subtask 1: 0 / 100