Submission #447258

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
447258	2021-07-25T15:00:48 Z	hungby04	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	362 ms	153476 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	150596 KB	Output is correct
2	Correct	68 ms	150564 KB	Output is correct
3	Correct	67 ms	150536 KB	Output is correct
4	Correct	80 ms	150704 KB	Output is correct
5	Correct	80 ms	150700 KB	Output is correct
6	Correct	87 ms	150716 KB	Output is correct
7	Correct	91 ms	150712 KB	Output is correct
8	Correct	183 ms	151576 KB	Output is correct
9	Correct	296 ms	152724 KB	Output is correct
10	Correct	315 ms	152756 KB	Output is correct
11	Correct	298 ms	152840 KB	Output is correct
12	Correct	306 ms	152684 KB	Output is correct
13	Correct	274 ms	153080 KB	Output is correct
14	Correct	300 ms	153164 KB	Output is correct
15	Correct	356 ms	153244 KB	Output is correct
16	Correct	362 ms	153212 KB	Output is correct
17	Correct	276 ms	153148 KB	Output is correct
18	Correct	279 ms	153176 KB	Output is correct
19	Correct	348 ms	153164 KB	Output is correct
20	Correct	355 ms	153476 KB	Output is correct