Submission #503109

#	Time	Username	Problem	Language	Result	Execution time	Memory
503109		KiriLL1ca	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	453 ms	208740 KiB

apple

#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define endl '\n'
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define sqr(x) ((ll)x)*((ll)x)
#define bcnt(X) __builtin_popcountll(X)

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 1e9 + 10;

struct ndo {
    struct node {
        node *l = nullptr, *r = nullptr;
        int sum = 0;
        bool psh = false;
    };

    node *root = new node();

    inline void push (node *v, int tl, int tr) {
        if (!v->l) v->l = new node();
        if (!v->r) v->r = new node();
        int tm = (tl + tr) >> 1;
        v->l->sum = tm - tl + 1;
        v->r->sum = tr - tm;
        v->psh = false;
        v->l->psh = v->r->psh = true;
    }

    inline void upd (node *v, int tl, int tr, int l, int r) {
        if (tl > r || l > tr) return;
        if (v->psh) push(v, tl, tr);
        if (l <= tl && tr <= r) {
            v->sum = tr - tl + 1;
            v->psh = true;
            push(v, tl, tr);
            return;
        }
        int tm = (tl + tr) >> 1;

        if (!v->l) v->l = new node();
        if (!v->r) v->r = new node();

        upd(v->l, tl, tm, l, r);
        upd(v->r, tm + 1, tr, l, r);
        v->sum = v->l->sum + v->r->sum;
    }

    inline int get (node *v, int tl, int tr, int l, int r) {
        if (tl > r || l > tr) return 0;

        if (v->psh) push(v, tl, tr);
        if (l <= tl && tr <= r) return v->sum;

        int tm = (tl + tr) >> 1;

        if (!v->l) v->l = new node();
        if (!v->r) v->r = new node();

        return get(v->l, tl, tm, l, r) + get(v->r, tm + 1, tr, l, r);
    }

    inline void upd (int l, int r) { upd(root, 0, N, l, r); }
    inline int get (int l, int r) { return get(root, 0, N, l, r); }
};

signed main ()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int q; cin >> q;
    int lst = 0;
    ndo st;
    while (q--) {
        int tp, l, r; cin >> tp >> l >> r;
        l += lst; r += lst;
        if (tp == 1) {
            lst = st.get(l, r);
            cout << lst << endl;
        }
        else {
            st.upd(l, r);
        }
    }
    return 0;
}

• Subtask 1: 100 / 100