Submission #1010285

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1010285	2024-06-28T16:20:17 Z	phoenix	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	159 ms	112596 KB

apple

#include <bits/stdc++.h>

using namespace std;

struct node {
    int l;
    int r;
    int s;
    bool upd;
    node() : l(0), r(0), s(0), upd(0) {}
};

const int A = (1 << 30) - 1;
const int MAX_SZ = 7'000'000;

int sz = 0;
node st[MAX_SZ];
/*
[2, 3]
[4, 5]
[1, 5]
*/

void setpush(int v, int l, int r) {
    st[v].s = r - l + 1;
    st[v].upd = true;
}

void push(int v, int l, int r) {
    int mid = (l + r) / 2;
    int L = st[v].l, R = st[v].r;
    if (!L) {
        assert(sz + 1 < MAX_SZ);
        L = st[v].l = ++sz;
        st[L] = node();
    }
    if (!R) {
        assert(sz + 1 < MAX_SZ);
        R = st[v].r = ++sz;
        st[R] = node();
    }
    if (!st[v].upd) return;
    setpush(L, l, mid);
    setpush(R, mid + 1, r);
    st[v].upd = false;
}

void update(int ql, int qr, int l = 0, int r = A, int v = 1) {
    if (r < ql || l > qr) 
        return;
    if (ql <= l && r <= qr) {
        setpush(v, l, r);
        return;
    }
    push(v, l, r);
    int mid = (l + r) / 2;
    update(ql, qr, l, mid, st[v].l);
    update(ql, qr, mid + 1, r, st[v].r);
    st[v].s = st[st[v].l].s + st[st[v].r].s;
}
int get(int ql, int qr, int l = 0, int r = A, int v = 1) {
    if (r < ql || l > qr) 
        return 0;
    if (ql <= l && r <= qr) {
        return st[v].s;
    }
    push(v, l, r);
    int mid = (l + r) / 2; 
    return get(ql, qr, l, mid, st[v].l) + get(ql, qr, mid + 1, r, st[v].r);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    st[++sz] = node();
    int M;
    cin >> M;
    int c = 0;
    while (M--) {
        int d, l, r;
        cin >> d >> l >> r;
        l += c, r += c;
        assert(0 <= l && r <= A);
        if (d == 1) {
            c = get(l, r);
            cout << c << '\n';
        } else {
            update(l, r);
        }
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	109904 KB	Output is correct
2	Correct	38 ms	109896 KB	Output is correct
3	Correct	24 ms	109908 KB	Output is correct
4	Correct	30 ms	109916 KB	Output is correct
5	Correct	31 ms	109904 KB	Output is correct
6	Correct	47 ms	109832 KB	Output is correct
7	Correct	30 ms	109904 KB	Output is correct
8	Correct	83 ms	110164 KB	Output is correct
9	Correct	109 ms	110160 KB	Output is correct
10	Correct	129 ms	110304 KB	Output is correct
11	Correct	141 ms	110408 KB	Output is correct
12	Correct	113 ms	110164 KB	Output is correct
13	Correct	105 ms	110416 KB	Output is correct
14	Correct	135 ms	110416 KB	Output is correct
15	Correct	126 ms	110364 KB	Output is correct
16	Correct	140 ms	112464 KB	Output is correct
17	Correct	124 ms	112596 KB	Output is correct
18	Correct	110 ms	112464 KB	Output is correct
19	Correct	159 ms	112464 KB	Output is correct
20	Correct	147 ms	112464 KB	Output is correct