# Clean C++ Code using SegmentTree and Discretization

• ``````#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
if(buildings.size() < 1)
return vector<pair<int, int>>();

set<int> s;

for (const auto & building : buildings)
{
s.insert(building[0]);
s.insert(building[1]);
s.insert(building[1] - 1);
}

unordered_map<int,int> idxs;
vector<int> nums(s.size());
int cnt = 0;
for(int num : s) {
nums[cnt] = num;
idxs[num] = cnt++;
}

vector<int> heights(cnt << 2);
build(heights, 0, cnt - 1, 1);

for (const auto & building : buildings)
{
int L = idxs[building[0]], R = idxs[building[1] - 1], h = building[2];
update(heights, L, R, h, 0, cnt - 1, 1);
}

vector<pair<int,int>> ret;
for(int i = 0,last = -1; i < cnt; i++)
{
int tmp = query(heights, i, 0, cnt- 1, 1);
if(tmp != last)
ret.push_back(pair<int,int>(nums[i], tmp));
last = tmp;
}
return ret;
}

void build(vector<int>& heights, int l, int r, int rt) {
if (l == r) {
heights[rt] = 0;
return;
}
int m = (l + r) >> 1;
build(heights, lson);
build(heights, rson);
}

void pushDown(vector<int>& heights, int rt) {
if (heights[rt] != 0) {
heights[rt << 1] = max(heights[rt], heights[rt << 1]);
heights[rt << 1 | 1] = max(heights[rt], heights[rt << 1 | 1]);
heights[rt] = 0;
}
}

void update(vector<int>& heights, int L, int R, int h, int l, int r, int rt) {
if (L <= l && r <= R) {
heights[rt] = max(heights[rt], h);
return;
}
pushDown(heights, rt);
int m = (l + r) >> 1;
if (L <= m) update(heights, L, R, h, lson);
if (R > m) update(heights, L, R, h, rson);
}

int query(vector<int>& heights, int idx, int l, int r, int rt) {
if (l == r) {
return heights[rt];
}
pushDown(heights, rt);
int m = (l + r) >> 1;
if (idx <= m) return query(heights, idx, lson);
else return query(heights, idx, rson);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.