LabASD ST G

#include <iostream>
#include <algorithm>
#include <vector>

struct line {
    int X;
    int type;
    int UY, DY;
};

struct node {
    node *left = nullptr;
    node *right = nullptr;
    int max, tAdd, L, R;

    node(int L, int R) {
        this->L = L;
        this->R = R;
        max = 0;
        tAdd = 0;
    }
};

void build_tree(node *cur, int deep, int cur_deep, int L, int R) {
    if (cur_deep != deep) {
        cur->left = new node(L, (L + R) / 2);
        cur->right = new node((L + R) / 2, R);
        build_tree(cur->left, deep, cur_deep + 1, L, (R + L) / 2);
        build_tree(cur->right, deep, cur_deep + 1, (L + R) / 2, R);
    }
}

void push(node *cur) {
    if (cur->tAdd) {
        if (cur->left != nullptr) {
            cur->left->tAdd += cur->tAdd;
            cur->right->tAdd += cur->tAdd;
        }
        cur->max += cur->tAdd;
        cur->tAdd = 0;
    }
}

void add(node *cur, int new_val, int L, int R) {
    push(cur);
    if (cur->L >= L && cur->R <= R) {
        cur->tAdd += new_val;
        push(cur);
        return;
    }
    if (cur->L >= R || cur->R <= L)
        return;
    add(cur->left, new_val, L, R);
    add(cur->right, new_val, L, R);
    cur->max = std::max(cur->left->max, cur->right->max);
}

std::pair<int, int> get_max(node *cur) {
    push(cur);
    if (cur->right != nullptr) {
        if (cur->max == cur->left->max + cur->left->tAdd)
            return get_max(cur->left);
        else
            return get_max(cur->right);
    }
    return std::make_pair(cur->max,cur->L);
};

bool comp(line A, line B) {
    if (A.X == B.X)
        if (A.type==1)
            return true;
        else if (B.type==1)
            return false;
        else
            return true;
    return A.X < B.X;
}

int main() {
    int n, min_y = INT_MAX, max_y = INT_MIN;
    node *head;
    std::vector<line> data;
    std::cin >> n;
    line tmp, tmp0;
    tmp.type = 1;
    tmp0.type = -1;
    for (int i = 0; i < n; i++) {
        std::cin >> tmp.X >> tmp.UY >> tmp0.X >> tmp.DY;
        tmp0.UY = tmp.UY;
        tmp0.DY = tmp.DY;
        max_y = std::max(max_y, tmp.DY);
        min_y = std::min(min_y, tmp.UY);
        data.push_back(tmp);
        data.push_back(tmp0);
    }
    n = max_y - min_y + 1;
    int deep = 1;
    while (!((1 << deep - 1) >= n)) {
        deep++;
    }
    std::stable_sort(data.begin(), data.end(), comp);
    head = new node(0, 1 << deep);
    build_tree(head, deep, 0, 0, 1 << deep);
    std::pair<int,int> ans;
    int maxX,maxY,max=INT_MIN;
    for (int i = 0; i < data.size(); i++) {
        add(head, data[i].type, data[i].UY-min_y, data[i].DY + 1-min_y);
        ans=get_max(head);
        if(max<ans.first){
            max=ans.first;
            maxY=ans.second+min_y;
            maxX=data[i].X;
        }
    }
    std::cout<<max<<"\n"<<maxX<<" "<<maxY;
}