# C++ discretization + Segment Tree O(nlog(n)) time 29ms

• ``````class Solution {
vector<int> vec;
int getId(int x) {
return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1;
}
int m;
int seg[2005 * 4], lazy[2005 * 4];

void build(int rt, int left, int right) {
seg[rt] = 0, lazy[rt] = -1;
if (left == right) return;
int mid = (left + right) / 2;
build(rt * 2, left, mid);
build(rt * 2 + 1, mid + 1, right);
}

void add(int rt, int left, int right, int L, int R, int val) {
if (L <= left && right <= R) {
seg[rt] = lazy[rt] = val;
return;
}
pushDown(rt, left, right);

int mid = (left + right) / 2;

if (L <= mid) add(rt * 2, left, mid, L, R, val);
if (R > mid) add(rt * 2 + 1, mid + 1, right, L, R, val);

seg[rt] = max(seg[rt * 2], seg[rt * 2 + 1]);
}

void pushDown(int rt, int left, int right) {
// use lazy symbol to reduce the segment tree traverse, only update the son when needed
if (lazy[rt] != -1) {
seg[rt * 2] = lazy[rt * 2] = lazy[rt * 2 + 1] = seg[rt * 2 + 1] = lazy[rt];
lazy[rt] = -1;
}
}

int query(int rt, int left, int right, int L, int R) {
if (L <= left && right <= R) {
return seg[rt];
}
pushDown(rt, left, right);

int mid = (left + right) / 2;

int res = -1;
if (L <= mid) res = max(res, query(rt * 2, left, mid, L, R));
if (R > mid) res = max(res, query(rt * 2 + 1, mid + 1, right, L, R));

return res;
}
public:
vector<int> fallingSquares(vector<pair<int, int>>& positions) {
int n = positions.size();

for (int i = 0; i < n; i++) {
vec.push_back(positions[i].first);
vec.push_back(positions[i].first + positions[i].second - 1);
}

//discretization
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());

m = vec.size();

//build tree
build(1, 1, m);

vector<int> res;
int curMax = 0;

//insert segment to tree and query
for (int i = 0; i < n; i++) {

//use discretization to reduce the size of segment tree
int l = getId(positions[i].first);
int r = getId(positions[i].first + positions[i].second - 1);

// query the maxHeight from l to r
int segMax = query(1, 1, m, l, r);

int newHeight = segMax + positions[i].second;

// add new height to segment tree from l to r
add(1, 1, m, l, r, newHeight);

curMax = max(curMax, newHeight);

res.push_back(curMax);
}

return res;
}
};
``````

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