Submission #636063

#	Time	Username	Problem	Language	Result	Execution time	Memory
636063		tvladm2009	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	2086 ms	84840 KiB

apple

#include <iostream>

using namespace std;

const int LIM = 1e9;

struct Node {
    Node *lson;
    Node *rson;
    int sum;
    bool lazy;
    int l;
    int r;

    Node(int st, int dr) {
        sum = 0;
        lazy = false;
        l = st;
        r = dr;
        lson = NULL;
        rson = NULL;
    }
};

void push(Node *v, Node *&lson, Node *&rson, int l, int r) {
    if (l == r) {
        return;
    }
    if (v->lazy == true) {
        int mid = (l + r) / 2;
        if (lson == NULL) {
            lson = new Node(l, mid);
        }
        if (rson == NULL) {
            rson = new Node(mid + 1, r);
        }
        lson->lazy = true;
        lson->sum = l - mid + 1;
        rson->lazy = true;
        rson->sum = r - mid;
        v->lazy = false;
    }
}

void update(Node *&root, int l, int r, int p, int q) {
    if (p > q) {
        return;
    }
    if (root == NULL) {
        root = new Node(l, r);
    }
    if (p <= l && r <= q) {
        root->lazy = true;
        root->sum = r - l + 1;
    } else {
        push(root, root->lson, root->rson, l, r);
        int mid = (l + r) / 2;
        update(root->lson, l, mid, p, min(mid, q));
        update(root->rson, mid + 1, r, max(p, mid + 1), q);
        int sumlson = 0, sumrson = 0;
        if (root->lson == NULL) {
            sumlson = 0;
        } else {
            sumlson = root->lson->sum;
        }
        if (root->rson == NULL) {
            sumrson = 0;
        } else {
            sumrson = root->rson->sum;
        }
        root->sum = sumlson + sumrson;
    }
}

int query(Node *&root, int l, int r, int p, int q) {
    if (p > q) {
        return 0;
    }
    if (root == NULL) {
        return 0;
    }
    if (q <= l && r <= q) {
        return root->sum;
    } else {
        push(root, root->lson, root->rson, l, r);
        int mid = (l + r) / 2;
        return query(root->lson, l, mid, p, min(mid, q)) + query(root->rson, mid + 1, r, max(p, mid + 1), q);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int q;
    cin >> q;
    int c = 0;
    Node *root = new Node(1, LIM);
    while (q--) {
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 1) {
            c = query(root, 1, LIM, x + c, y + c);
            cout << c << "\n";
        } else {
            update(root, 1, LIM, x + c, y + c);
        }
    }
    return 0;
}

• Subtask 1: 0 / 100