Submission #467210

#	Time	Username	Problem	Language	Result	Execution time	Memory
467210		Rico64	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	1 ms	332 KiB

apple

#include <iostream>

const int MAX_SIZE = 1073741824;

using namespace std;

struct node {
    node *l, *r;
    int c;
    node() : l(nullptr), r(nullptr), c(0) {}
    ~node() {
        delete l;
        delete r;
        delete &c;
    }
} *root;

void qpaint(node *v, int l, int r, int sz) {
    if (l >= sz || r <= 0 || v->c == sz) return;
    if (l <= 0 && r >= sz) {
        v->c = sz;
        delete v->l;
        delete v->r;
        v->l = v->r = nullptr;
        return;
    }
    if (v->l == nullptr) {
        v->l = new node();
        v->r = new node();
    }
    qpaint(v->l, l, r, sz >> 1);
    qpaint(v->r, l - (sz >> 1), r - (sz >> 1), sz >> 1);
    v->c = v->l->c + v->r->c;
}

int qcount(node *v, int l, int r, int sz) {
    if (l >= sz || r <= 0 || v->c == 0) return 0;
    if (l <= 0 && r >= sz) {
        return v->c;
    }
    if (v->l == nullptr) {
        v->l = new node();
        v->r = new node();
        v->l->c = v->r->c = sz >> 1;
    }
    return qcount(v->l, l, r, sz >> 1) + qcount(v->r, l - (sz >> 1), r - (sz >> 1), sz >> 1);
}

int main() {
    int ql;
    cin >> ql;
    root = new node();
    int c = 0;
    for (int it = 0, type; it < ql; ++it) {
        cin >> type;
        if (type == 1) {
            int l, r;
            cin >> l >> r;
            c = qcount(root, l - 1 + c, r + c, MAX_SIZE);
            cout << c << endl;
        } else if (type == 2) {
            int l, r;
            cin >> l >> r;
            qpaint(root, l - 1 + c, r + c, MAX_SIZE);
        }
    }

    return 0;
}

• Subtask 1: 0 / 100