Submission #1010279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010279		phoenix	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	64 ms	127572 KiB

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 << 20) - 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