leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0699.cpp (1611B)

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