Submission #1004718

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

apple

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define endl "\n"
#define ll long long
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr);

const int R = 1e9 + 5;

struct Node {
    int val;
    bool lazy;
    struct Node* left;
    struct Node* right;
};

void compose(Node* parent, Node* node) {
    node->lazy |= parent->lazy;
}

void apply(Node* node, int l, int r) {
    if (node->lazy) {
        node->val = r - l + 1;
    }
    if (l != r) {
        if (node->left == nullptr) {
            node->left = new Node();
        }
        compose(node, node->left);
        if (node->right == nullptr) {
            node->right = new Node();
        }
        compose(node, node->right);
    }
    node->lazy = false;
}

void setUpdate(Node* node, int l, int r, int lq, int rq) {
    if (l > rq || lq > r) {
        return;
    }
    if (lq <= l && rq >= r) {
        node->lazy = true;
        return;
    }
    int mid = (l + r) / 2;
    apply(node, l, r);
    if (node->left == nullptr) {
        node->left = new Node();
    }
    setUpdate(node->left, l, mid, lq, rq);

    if (node->right == nullptr) {
        node->right = new Node();
    }
    setUpdate(node->right, mid + 1, r, lq, rq);

    apply(node->left, l, mid);
    apply(node->right, mid + 1, r);
    node->val = 0;
    if (node->left != nullptr) {
        node->val += node->left->val;
    }
    if (node->right != nullptr) {
        node->val += node->right->val;
    }
}

int query(Node* node, int l, int r, int lq, int rq) {
    if (r < lq || l > rq) {
        return 0;
    }
    apply(node, l, r);

    if (lq <= l && rq >= r) {
        return node->val;
    }

    int mid = (l + r) / 2, ans = 0;
    if (node->left != nullptr) {
        ans += query(node->left, l, mid, lq, rq);
    }
    if (node->right != nullptr) {
        ans += query(node->right, mid + 1, r, lq, rq);
    }
    return ans;
}

int main() {
    IOS;
    struct Node* root = new Node();
    int q;
    cin >> q;
    int c = 0;
    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
        if (t == 2) {
            int l, r;
            cin >> l >> r;
            setUpdate(root, 0, R - 1, l + c, r + c);
        } else {
            int l, r;
            cin >> l >> r;
            int q = query(root, 0, R - 1, l + c, r + c);
            cout << q << endl;
            c += q;
        }
    }
    return 0;
}

• Subtask 1: 0 / 100