Submission #1010276

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1010276	2024-06-28T16:12:06 Z	phoenix	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	120 ms	63488 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];


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	13 ms	63068 KB	Output is correct
2	Correct	10 ms	62880 KB	Output is correct
3	Correct	10 ms	63068 KB	Output is correct
4	Correct	16 ms	62904 KB	Output is correct
5	Correct	17 ms	63064 KB	Output is correct
6	Correct	18 ms	63068 KB	Output is correct
7	Correct	17 ms	63064 KB	Output is correct
8	Correct	52 ms	63068 KB	Output is correct
9	Correct	115 ms	63404 KB	Output is correct
10	Correct	99 ms	63440 KB	Output is correct
11	Correct	104 ms	63316 KB	Output is correct
12	Correct	102 ms	63388 KB	Output is correct
13	Correct	107 ms	63316 KB	Output is correct
14	Correct	103 ms	63488 KB	Output is correct
15	Incorrect	120 ms	63296 KB	Output isn't correct
16	Halted	0 ms	0 KB	-