Submission #1175941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175941		matus192	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	323 ms	137280 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 {
    int val;
    bool cele;
    Node *lson, *rson;
    Node() {
        lson = NULL;
        rson = NULL;
        val = 0;
        cele = false;
    }
};

void remove(Node *cur, int l, int r) {
    if (!cur->lson) cur->lson = new Node();
    if (!cur->rson) cur->rson = new Node();
    if (!cur->cele) return;
    int m = (l + r) / 2;
    cur->lson->cele = true;
    cur->rson->cele = true;
    cur->lson->val = m - l;
    cur->rson->val = r - m;
}

int sum(Node *cur, int vl, int vr, int l, int r) {
    if (vr <= l || vl >= r) return 0;
    if (vl <= l && vr >= r) return cur->val;
    remove(cur, l, r);
    int m = (l + r) / 2;
    int lans = sum(cur->lson, vl, vr, l, m);
    int rans = sum(cur->rson, vl, vr, m, r);
    return lans + rans;
}

void prepni(Node *cur, int vl, int vr, int l, int r) {
    if (vr <= l || vl >= r) return;
    if (vl <= l && vr >= r) {
        cur->cele = true;
        cur->val = r - l;
        return;
    }
    remove(cur, l, r);
    int m = (l + r) / 2;
    prepni(cur->lson, vl, vr, l, m);
    prepni(cur->rson, vl, vr, m, r);
    cur->val = cur->lson->val + cur->rson->val;
}

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

    return 0;
}

• Subtask 1: 100 / 100