0699.cpp (1611B)
1 class SegmentTree { 2 const int n; 3 vector<int> t = vector<int>(2 * n); 4 5 public: 6 SegmentTree(int n) : n(n) {} 7 8 int sum(int l, int r) const { 9 int res = 0; 10 11 for (l += n, r += n; l < r; l /= 2, r /= 2) { 12 if (l & 1) res = max(res, t[l++]); 13 if (r & 1) res = max(res, t[--r]); 14 } 15 16 return res; 17 } 18 19 void update(int p, int val) { 20 for (t[p += n] = val; p > 1; p /= 2) 21 t[p / 2] = max(t[p], t[p ^ 1]); 22 } 23 }; 24 25 class Solution { 26 public: 27 vector<int> fallingSquares(const vector<vector<int>> &positions) const { 28 vector<int> possible; 29 for (const auto &pos : positions) { 30 possible.push_back(pos[0]); 31 possible.push_back(pos[0] + pos[1]); 32 } 33 34 const int m = size(possible); 35 static int idxs[2001]; 36 iota(idxs, idxs + m, 0); 37 sort(idxs, idxs + m, [&](int a, int b) { return possible[a] < possible[b]; }); 38 39 static int rev[2001]; 40 for (int i = m - 2, cnt = rev[idxs[m - 1]] = m - 1; i >= 0; i--) { 41 if (possible[idxs[i]] != possible[idxs[i + 1]]) cnt--; 42 rev[idxs[i]] = cnt; 43 } 44 45 int maxi = 0; 46 vector<int> res; 47 SegmentTree seg(m); 48 for (int i = 0; i < size(positions); i++) { 49 const int a = rev[i * 2], b = rev[i * 2 + 1]; 50 const int crnt = positions[i][1] + seg.sum(a, b); 51 res.push_back(maxi = max(maxi, crnt)); 52 for (int i = a; i < b; i++) { 53 seg.update(i, crnt); 54 } 55 } 56 57 return res; 58 } 59 };