Submission #1190786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190786		TheGreatAntivirus	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	289 ms	263596 KiB

apple

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define stdI freopen("input.txt", "r", stdin);
#define stdO freopen("output.txt", "w", stdout);
#define all(x) x.begin(), x.end()
#define mp(x, y) make_pair(x, y)
#define int long long
#define F first
#define S second

#ifdef OMAIN
#include <tools/debug.h>
#else
#define dbg(...)
#define ddbg(...)
#endif

using namespace std;
using namespace __gnu_pbds;

template<typename T, template<typename> class order = less>
using ordered_set = tree<T,
    null_type, order<T>, rb_tree_tag,
    tree_order_statistics_node_update>;

typedef pair<int, int> pii;

const int MAXN = 1 << 30, MAXLOG = 18, MAXSQ = 500, INF = 1e18, MOD = 1e9 + 7;

struct segment
{
    struct node
    {
        int q = 0, lzy = 0, lc = -1, rc = -1;
    };
    vector<node> sg; int root;
    segment()
    {
        sg.emplace_back(); root = 0;
    }
    void push(int v, int vl, int vr)
    {
        if(sg[v].lzy != 0)
        {
            sg[v].q = sg[v].lzy; sg[v].lzy = 0;
            if(vl == vr)
            {
                return;
            }
            if(sg[v].lc == -1)
            {
                sg[v].lc = sg.size(); sg.emplace_back();
            }
            if(sg[v].rc == -1)
            {
                sg[v].rc = sg.size(); sg.emplace_back();
            }
            int val = (vr - vl + 1) >> 1;
            sg[sg[v].lc].lzy = sg[sg[v].rc].lzy = val;
        }
    }
    void update(int v, int vl, int vr, int l, int r)
    {
        if(v == -1)
        {
            return;
        }
        push(v, vl, vr);
        if(vl > r || vr < l)
        {
            return;
        }
        if(l <= vl && vr <= r)
        {
            sg[v].lzy = vr - vl + 1;
            push(v, vl, vr);
            return;
        }
        int mid = (vl + vr) >> 1;
        if(sg[v].lc == -1)
        {
            sg[v].lc = sg.size(); sg.emplace_back();
        }
        if(sg[v].rc == -1)
        {
            sg[v].rc = sg.size(); sg.emplace_back();
        }
        update(sg[v].lc, vl, mid, l, r); update(sg[v].rc, mid + 1, vr, l, r);
        int lq = sg[v].lc == -1 ? 0 : sg[sg[v].lc].q;
        int rq = sg[v].rc == -1 ? 0 : sg[sg[v].rc].q;
        sg[v].q = lq + rq;
    }
    int get(int v, int vl, int vr, int l, int r)
    {
        if(v == -1)
        {
            return 0;
        }
        push(v, vl, vr);
        if(vl > r || vr < l)
        {
            return 0;
        }
        if(l <= vl && vr <= r)
        {
            return sg[v].q;
        }
        int mid = (vl + vr) >> 1;
        return get(sg[v].lc, vl, mid, l, r) + get(sg[v].rc, mid + 1, vr, l, r);
    }
} s;

void solve()
{
    int q, c = 0; cin >> q;
    while(q--)
    {
        int tp; cin >> tp;
        if(tp == 1)
        {
            int l, r; cin >> l >> r; l += c - 1; r += c - 1;
            c = s.get(0, 0, MAXN - 1, l, r);
            cout << c << "\n";
        }
        else
        {
            int l, r; cin >> l >> r; l += c - 1; r += c - 1;
            s.update(0, 0, MAXN - 1, l, r);
        }
    }
}

int32_t main()
{
    IOS;
    int t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
    #ifdef OMAIN
        cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
    return 0;
}

• Subtask 1: 0 / 100