Submission #579349

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
579349	2022-06-19T02:37:06 Z	minhi1	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	290 ms	186504 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 = 123456;
struct node {
    int sum, lz, lc, rc, l, r;
    node() : sum(0), lz(0), lc(-1), rc(-1) {}
} st[64 * N];
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);
    sol();
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	185804 KB	Output is correct
2	Correct	78 ms	185836 KB	Output is correct
3	Correct	76 ms	185788 KB	Output is correct
4	Correct	84 ms	185776 KB	Output is correct
5	Correct	84 ms	185804 KB	Output is correct
6	Correct	84 ms	185760 KB	Output is correct
7	Correct	88 ms	185804 KB	Output is correct
8	Correct	140 ms	186064 KB	Output is correct
9	Correct	230 ms	186340 KB	Output is correct
10	Correct	233 ms	186192 KB	Output is correct
11	Correct	230 ms	186152 KB	Output is correct
12	Correct	233 ms	186208 KB	Output is correct
13	Correct	220 ms	186420 KB	Output is correct
14	Correct	219 ms	186392 KB	Output is correct
15	Correct	272 ms	186440 KB	Output is correct
16	Correct	287 ms	186444 KB	Output is correct
17	Correct	217 ms	186444 KB	Output is correct
18	Correct	221 ms	186416 KB	Output is correct
19	Correct	290 ms	186444 KB	Output is correct
20	Correct	288 ms	186504 KB	Output is correct