#include <iostream>
#include <string>
#include <cstdio>
#include <list>
#include <vector>

using namespace std;

class Solution {
    void merge(vector<pair<int, int>>& lhs, vector<pair<int, int>>& rhs, vector<pair<int, int>>& result) {
        int m = (int)lhs.size();
        int n = (int)rhs.size();

        int i = 0, j = 0;
        while(i < m and j < n) {
            int k = (int)result.size() - 1;
            if(lhs[i] < rhs[j]) {

                if(result.empty() or result[k].first < lhs[i].first) {
                    result.push_back(lhs[i++]);
                    if(i < m and lhs[i].first - lhs[i - 1].first > 0) {
                        result.push_back({lhs[i].first - 1, lhs[i - 1].second});
                    }
                }
                else if(lhs[i].first == result[k].first) {
                    result[k].second = max(result[k].second, lhs[i].second);
                    ++i;
                    if(i < m and lhs[i].first - lhs[i - 1].first > 0) {
                        result.push_back({lhs[i].first - 1, lhs[i - 1].second});
                    }
                }
                else if(lhs[i].first < result[k].first) {
                    if(lhs[i].second <= result[k].second) {
                        ++i;
                        if(i < m and lhs[i].first - lhs[i - 1].first > 0 and lhs[i].first - 1 > result[k].first) {
                            result.push_back({result[k].first, lhs[i - 1].second});
                            result.push_back({lhs[i].first - 1, lhs[i - 1].second});
                        }
                    }
                    else {
                        pair<int, int> elem = result[k];
                        result[k] = lhs[i++];
                        if(i < m and lhs[i].first - lhs[i - 1].first > 0) {
                            if(lhs[i].first - 1 < elem.first) {
                                result.push_back({lhs[i].first - 1, elem.second});
                                result.push_back(elem);
                            }
                            else if(lhs[i].first - 1 > elem.first) {
                                result.push_back({lhs[i].first - 1, lhs[i - 1].second});
                            }
                            else {
                                result.push_back({lhs[i].first - 1, lhs[i - 1].second});
                            }
                        }
                    }
                }

            }
            else {

                if(result.empty() or result[k].first < rhs[j].first) {
                    result.push_back(rhs[j++]);
                    if(j < n and rhs[j].first - rhs[j - 1].first > 0) {
                        result.push_back({rhs[j].first - 1, rhs[j - 1].second});
                    }
                }
                else if(rhs[j].first == result[k].first) {
                    result[k].second = max(result[k].second, rhs[j].second);
                    ++j;
                    if(j < n and rhs[j].first - rhs[j - 1].first > 0) {
                        result.push_back({rhs[j].first - 1, rhs[j - 1].second});
                    }
                }
                else if(rhs[j].first < result[k].first) {
                    if(rhs[j].second <= result[k].second) {
                        ++j;
                        if(j < n and rhs[j].first - rhs[j - 1].first > 0 and rhs[j].first - 1 > result[k].first) {
                            result.push_back({result[k].first, rhs[j - 1].second});
                            result.push_back({rhs[j].first - 1, rhs[j - 1].second});
                        }
                    }
                    else {
                        pair<int, int> elem = result[k];
                        result[k] = rhs[j++];
                        if(j < n and rhs[j].first - rhs[j - 1].first > 0) {
                            if(rhs[j].first - 1 < elem.first) {
                                result.push_back({rhs[j].first - 1, elem.second});
                                result.push_back(elem);
                            }
                            else if(rhs[j].first - 1 > elem.first) {
                                result.push_back({rhs[j].first - 1, rhs[j - 1].second});
                            }
                            else {
                                result.push_back({rhs[j].first - 1, rhs[j - 1].second});
                            }
                        }
                    }
                }

            }
        }

        while(i < m) {
            result.push_back(lhs[i++]);
        }
        while(j < n) {
            result.push_back(rhs[j++]);
        }
    }

    void compress(vector<pair<int, int>>& result) {
        vector<pair<int, int>> tmp;
        int n = (int)result.size();
        for(int i = 0; i < n; ++i) {
            int height = result[i].second;
            tmp.push_back(result[i]);
            while(i + 1 < n and result[i + 1].second == height) {
                ++i;
            }
        }
        result.clear();
        result.insert(result.end(), tmp.begin(), tmp.end());
    }

    vector<pair<int, int>> getSkyline(int left, int right, vector<vector<int>> const& buildings) {
        if(left == right) {
            vector<pair<int, int>> result;
            result.push_back({buildings[left][0], buildings[left][2]});
            if(buildings[left][2] > 0) {
                result.push_back({buildings[left][1], 0});
            }
            return result;
        }
        int mid = left + (right - left) / 2;
        vector<pair<int, int>> leftline = getSkyline(left, mid, buildings);
        vector<pair<int, int>> rightline = getSkyline(mid + 1, right, buildings);

        vector<pair<int, int>> result;
        merge(leftline, rightline, result);
        compress(result);

        return result;
    }

public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        vector<pair<int, int>> result;
        if(buildings.empty()) return result;

        sort(buildings.begin(), buildings.end());
        int n = (int)buildings.size();
        result = getSkyline(0, n - 1, buildings);

        return result;
    }
};



int main(void) {
    vector<vector<int>> v{{2, 9, 10}, {3, 7, 15}, {5, 12, 12}, {15, 20, 10}, {19, 24, 8}};
    vector<pair<int, int>> result = Solution().getSkyline(v);
    return 0;
}