Submission #579350

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
579350	2022-06-19T02:37:38 Z	minhi1	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	283 ms	186340 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);
//    #ifdef DHT
//        freopen("hehe.inp", "r", stdin);
//    #else
//        freopen("f.in", "r", stdin); freopen("f.out", "w", stdout);
//    #endif
    sol();
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	74 ms	185804 KB	Output is correct
2	Correct	75 ms	185804 KB	Output is correct
3	Correct	75 ms	185840 KB	Output is correct
4	Correct	84 ms	185872 KB	Output is correct
5	Correct	83 ms	185852 KB	Output is correct
6	Correct	83 ms	185880 KB	Output is correct
7	Correct	87 ms	185768 KB	Output is correct
8	Correct	148 ms	186080 KB	Output is correct
9	Correct	233 ms	186248 KB	Output is correct
10	Correct	234 ms	186236 KB	Output is correct
11	Correct	232 ms	186184 KB	Output is correct
12	Correct	241 ms	186224 KB	Output is correct
13	Correct	216 ms	186340 KB	Output is correct
14	Correct	224 ms	186316 KB	Output is correct
15	Correct	278 ms	186320 KB	Output is correct
16	Correct	283 ms	186224 KB	Output is correct
17	Correct	228 ms	186248 KB	Output is correct
18	Correct	220 ms	186224 KB	Output is correct
19	Correct	281 ms	186248 KB	Output is correct
20	Correct	275 ms	186332 KB	Output is correct