Submission #579347

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
579347	2022-06-19T02:34:46 Z	minhi1	Monkey and Apple-trees (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

#	Verdict	Execution time	Memory	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	-