답안 #579347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
579347	2022-06-19T02:34:46 Z	minhi1	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	302 ms	191432 KB

apple

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const ll linf = 1e18;
const int inf = (int)1e9 + 25;
/////////////////////////////////////////////////
const int N = 1e6 + 25;
struct node {
    int sum, lz, lc, rc, l, r;
    node() : sum(0), lz(0), lc(-1), rc(-1) {}
} st[4000025];
int m, cnt = 2;
void pushdown(int i) {
    if (st[i].lz == 1) {
        st[st[i].lc].sum = st[st[i].lc].r - st[st[i].lc].l + 1;
        st[st[i].lc].lz = 1;
        st[st[i].rc].sum = st[st[i].rc].r - st[st[i].rc].l + 1;
        st[st[i].rc].lz = 1;
        st[i].lz = 0;
    }
}
void upd(int i, int u, int v) {
    if (u == st[i].l && v == st[i].r) {
        st[i].sum = v - u + 1;
        st[i].lz = 1;
        return;
    }
    int mid = (st[i].l + st[i].r) >> 1;
    if (st[i].lc == -1) {
        st[i].lc = cnt++;
        st[st[i].lc].l = st[i].l;
        st[st[i].lc].r = mid;
    }
    if (st[i].rc == -1) {
        st[i].rc = cnt++;
        st[st[i].rc].l = mid + 1;
        st[st[i].rc].r = st[i].r;
    }
    pushdown(i);
    if (u > mid) upd(st[i].rc, u, v);
    else if (v <= mid) upd(st[i].lc, u, v);
    else {
        upd(st[i].lc, u, mid); upd(st[i].rc, mid + 1, v);
    }
    st[i].sum = st[st[i].lc].sum + st[st[i].rc].sum;
}
int get(int i, int u, int v) {
    if (u == st[i].l && v == st[i].r) return st[i].sum;
    int mid = (st[i].l + st[i].r) >> 1;
    if (st[i].lc == -1) {
        st[i].lc = cnt++;
        st[st[i].lc].l = st[i].l;
        st[st[i].lc].r = mid;
    }
    if (st[i].rc == -1) {
        st[i].rc = cnt++;
        st[st[i].rc].l = mid + 1;
        st[st[i].rc].r = st[i].r;
    }
    pushdown(i);
    if (u > mid) return get(st[i].rc, u, v);
    else if (v <= mid) return get(st[i].lc, u, v);
    else {
        return get(st[i].lc, u, mid) + get(st[i].rc, mid + 1, v);
    }
}
void sol() {
    cin >> m;
    st[1].sum = 0; st[1].lz = 0;
    st[1].l = 1; st[1].r = (int)1e9;
    int c = 0;
    while (m--) {
        int cmd, l, r;
        cin >> cmd >> l >> r;
        if (cmd == 1) {
            c = get(1, l + c, r + c);
            cout << c << '\n';
        }
        else {
            upd(1, l + c, r + c);
        }
    }
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
//    #ifdef DHT
//        freopen("hehe.inp", "r", stdin);
//    #else
//        freopen("f.in", "r", stdin); freopen("f.out", "w", stdout);
//    #endif
    sol();
    return 0;
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	94168 KB	Output is correct
2	Correct	39 ms	94184 KB	Output is correct
3	Correct	38 ms	94260 KB	Output is correct
4	Correct	45 ms	94324 KB	Output is correct
5	Correct	48 ms	94304 KB	Output is correct
6	Correct	60 ms	94348 KB	Output is correct
7	Correct	55 ms	94380 KB	Output is correct
8	Correct	143 ms	94560 KB	Output is correct
9	Correct	196 ms	94744 KB	Output is correct
10	Correct	198 ms	94632 KB	Output is correct
11	Correct	219 ms	94668 KB	Output is correct
12	Correct	205 ms	94660 KB	Output is correct
13	Correct	204 ms	94764 KB	Output is correct
14	Correct	202 ms	94760 KB	Output is correct
15	Runtime error	302 ms	191432 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-