Submission #1010282

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1010282	2024-06-28T16:18:14 Z	phoenix	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	116 ms	63572 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 = 4'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) {
        L = st[v].l = ++sz;
        st[L] = node();
    }
    if (!R) {
        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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	63320 KB	Output is correct
2	Correct	8 ms	63068 KB	Output is correct
3	Correct	9 ms	63068 KB	Output is correct
4	Correct	14 ms	63068 KB	Output is correct
5	Correct	15 ms	63084 KB	Output is correct
6	Correct	18 ms	62908 KB	Output is correct
7	Correct	17 ms	63064 KB	Output is correct
8	Correct	54 ms	63068 KB	Output is correct
9	Correct	106 ms	63304 KB	Output is correct
10	Correct	107 ms	63316 KB	Output is correct
11	Correct	107 ms	63364 KB	Output is correct
12	Correct	106 ms	63208 KB	Output is correct
13	Correct	107 ms	63312 KB	Output is correct
14	Correct	106 ms	63572 KB	Output is correct
15	Incorrect	116 ms	63316 KB	Output isn't correct
16	Halted	0 ms	0 KB	-