LabASD ST I

#include <iostream>
#include <limits>
#include <vector>
#include <deque>

using namespace std;

typedef long long type;

const type zero = numeric_limits<type>::max();
int size;

struct border {
    int left;
    int right;

    border(int left, int right);

    operator bool() const;

    inline int mid() const;
    inline int length() const;

    bool in(const border& other) const;
    bool out(const border& other) const;
};

struct node {
private:
    node* left = nullptr;
    node* right = nullptr;

public:
    border section;

    type sum = 0;
    type new_value = zero;
    type max_height = 0;

    node() = default;
    explicit node(const border& section);
    node(int left, int right);
    ~node();

    void push();
    int query(int height);
    void set(border request, int value);
};

node* root = nullptr;

int main() {
    ios_base::sync_with_stdio(false);
    cin >> size;

    root = new node(0, size - 1);

    char command;
    int left_border, right_border;
    int value;
    int height;

    while (cin >> command) {
        switch (command) {
            case 'I':
                cin >> left_border >> right_border >> value;
                root->set(border(left_border - 1, right_border - 1), value);
                break;
            case 'Q':
                cin >> height;
                cout << root->query(height) << endl;
                break;
            case 'E':
                delete root;
                return 0;
        }
    }

    delete root;
    return 0;
}

border::border(int left, int right) : left(left), right(right) {}

border::operator bool() const {
    return left != right;
}

inline int border::mid() const {
    return left + (right - left) / 2;
}

inline int border::length() const {
    return right - left + 1;
}

bool border::in(const border& other) const {
    return other.left <= left && right <= other.right;
}

bool border::out(const border& other) const {
    return other.right < left || right < other.left;
}

node::node(const border& section) : section(section) {}

node::node(int left, int right) : section(left, right) {}

node::~node() {
    if (left) {
        delete left;
    }

    if (right) {
        delete right;
    }
}

void node::push() {
    if (section) {
        if (!left) {
            left = new node(border(section.left, section.mid()));
        }

        if (!right) {
            right = new node(border(section.mid() + 1, section.right));
        }
    }

    if (new_value != zero) {
        sum = new_value * section.length();
        max_height = sum;

        if (section) {
            left->new_value = new_value;
            right->new_value = new_value;
        }

        new_value = zero;
    }
}

int node::query(int height) {
    push();

    if (max_height <= height) {
        return section.length();
    }

    if (!section) {
        return 0;
    }

    left->push();
    if (left->max_height > height) {
        return left->query(height);
    }

    return left->section.length() + right->query(height - (int) left->sum);
}

void node::set(border request, int value) {
    push();

    if (section.out(request)) {
        return;
    }

    if (section.in(request)) {
        new_value = value;
        push();
        return;
    }

    left->set(request, value);
    right->set(request, value);

    sum = left->sum + right->sum;
    max_height = max(left->max_height, left->sum + right->max_height);
}