oj.uz

답안 #447258

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
447258 2021-07-25T15:00:48 Z hungby04 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 362 ms 153476 KB 
/// 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

# 결과 실행 시간 메모리 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