Submission #503109

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
503109	2022-01-07T09:31:08 Z	KiriLL1ca	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	453 ms	208740 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	312 KB	Output is correct
4	Correct	15 ms	5020 KB	Output is correct
5	Correct	16 ms	6092 KB	Output is correct
6	Correct	15 ms	5868 KB	Output is correct
7	Correct	22 ms	6088 KB	Output is correct
8	Correct	122 ms	44932 KB	Output is correct
9	Correct	253 ms	78424 KB	Output is correct
10	Correct	266 ms	86412 KB	Output is correct
11	Correct	319 ms	92680 KB	Output is correct
12	Correct	277 ms	95456 KB	Output is correct
13	Correct	255 ms	110784 KB	Output is correct
14	Correct	260 ms	111560 KB	Output is correct
15	Correct	430 ms	202752 KB	Output is correct
16	Correct	432 ms	204228 KB	Output is correct
17	Correct	264 ms	115212 KB	Output is correct
18	Correct	298 ms	115368 KB	Output is correct
19	Correct	445 ms	208732 KB	Output is correct
20	Correct	453 ms	208740 KB	Output is correct