leetcode

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 };