Submission #1010271

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1010271	2024-06-28T16:02:22 Z	phoenix	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	119 ms	65872 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) {}
    node(int l, int r);
};

const int A = 1e9 + 10;
const int MAX_SZ = 4'000'000;

int sz = 0;
node st[MAX_SZ];

node::node(int l, int r) {
    this->l = l, this->r = r;
    this->s = st[l].s + st[r].s;
};

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;
        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	11 ms	63068 KB	Output is correct
2	Correct	9 ms	63068 KB	Output is correct
3	Correct	9 ms	62880 KB	Output is correct
4	Correct	16 ms	63068 KB	Output is correct
5	Correct	16 ms	63068 KB	Output is correct
6	Correct	15 ms	63064 KB	Output is correct
7	Correct	16 ms	63068 KB	Output is correct
8	Correct	55 ms	63948 KB	Output is correct
9	Correct	102 ms	65104 KB	Output is correct
10	Correct	108 ms	65200 KB	Output is correct
11	Correct	105 ms	65104 KB	Output is correct
12	Correct	107 ms	65108 KB	Output is correct
13	Correct	100 ms	65380 KB	Output is correct
14	Correct	89 ms	65616 KB	Output is correct
15	Incorrect	119 ms	65872 KB	Output isn't correct
16	Halted	0 ms	0 KB	-