Submission #447258

#	Time	Username	Problem	Language	Result	Execution time	Memory
447258		hungby04	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	362 ms	153476 KiB

apple

/// HuDzG
#include <bits/stdc++.h>
#define reset(a) memset(a,0,sizeof(a))
#define ll long long
#define ld long double
#define endl '\n'
#define AutoAC int main()
#define OO 1000000000000000000
#define F first
#define S second
#define pii pair <ll, ll>
#define pb push_back
#define nmax 100005
#define HUNGIT "C"
#define MOD 998244353

using namespace std;

const ll M = 1000001;

struct pp
{
    int sum, lazy, l, r, node_l = -1, node_r = -1;
} ST[64 * nmax];

int cnt = 0;

void Add(int l, int r)
{
    ST[++cnt] = {0, 0, l, r, -1, -1};
}

void Down(int id)
{
    int tmp = ST[id].lazy, l = ST[id].l, r = ST[id].r;
    int mid = (l + r) / 2;
    if (ST[id].node_l == -1) 
    {
        Add(l, mid);
        ST[id].node_l = cnt;
    }
    if (ST[id].node_r == -1) 
    {
        Add(mid + 1, r);
        ST[id].node_r = cnt;
    }
    if (tmp == 0) return;

    ST[ST[id].node_l].sum = (mid - l + 1);
    ST[ST[id].node_l].lazy = 1;

    ST[ST[id].node_r].sum = (r - mid);
    ST[ST[id].node_r].lazy = 1;

    ST[id].lazy = 0;
}

void Update(int id, int x, int y)
{
    if (ST[id].r < x || ST[id].l > y) return;
    if (x <= ST[id].l && ST[id].r <= y)
    {
        ST[id].sum = (ST[id].r - ST[id].l + 1);
        ST[id].lazy = 1;
        return;
    }
    Down(id);
    Update(ST[id].node_l, x, y);
    Update(ST[id].node_r, x, y);
    ST[id].sum = ST[ST[id].node_l].sum + ST[ST[id].node_r].sum;
}

int Get(int id, int x, int y)
{
    if (ST[id].r < x || ST[id].l > y) return 0;
    if (x <= ST[id].l && ST[id].r <= y) return ST[id].sum;
    Down(id);
    return Get(ST[id].node_l, x, y) + Get(ST[id].node_r, x, y);
}

void solve()
{
    int m, c = 0;
    Add(1, 1e9);
    cin >> m;
    while (m--)
    {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1)
        {
            c = Get(1, l + c, r + c);
            cout << c << endl;
        }
        else Update(1, l + c, r + c);
    }
}


AutoAC
{
    // clock_t START, FINISH;
    // START = clock();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen (HUNGIT".inp", "r", stdin);
    // freopen (HUNGIT".out", "w", stdout);
    ll T = 1;

    // cin >> T;

    for (int i = 1; i <= T; i++)
    {
        solve();
    }
    // FINISH = clock();
    // cout << fixed << setprecision(4);
    // cout << endl << "TIME: " << (ld)((ld)(FINISH - START) / CLOCKS_PER_SEC);
    return 0;
}
/*


4 1 3 2

 */

• Subtask 1: 100 / 100