Submission #579345

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
579345	2022-06-19T02:32:56 Z	minhi1	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	336 ms	193588 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("morse.inp", "r", stdin); freopen("morse.out", "w", stdout);
    #endif
    sol();
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	94156 KB	Output is correct
2	Correct	39 ms	94232 KB	Output is correct
3	Correct	42 ms	94156 KB	Output is correct
4	Correct	49 ms	94364 KB	Output is correct
5	Correct	55 ms	94408 KB	Output is correct
6	Correct	49 ms	94412 KB	Output is correct
7	Correct	49 ms	94332 KB	Output is correct
8	Correct	111 ms	95188 KB	Output is correct
9	Correct	198 ms	96396 KB	Output is correct
10	Correct	204 ms	96372 KB	Output is correct
11	Correct	201 ms	96284 KB	Output is correct
12	Correct	221 ms	96304 KB	Output is correct
13	Correct	179 ms	96696 KB	Output is correct
14	Correct	192 ms	96764 KB	Output is correct
15	Runtime error	336 ms	193588 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-