Find the Longest Valid Obstacle Course at Each Position LeetCode solution in C++

1
class Solution {
2
 public:
3
  // ranking each element to make segment tree of small size
4
  void compress(vector<int> &a) {
5
    vector<int> b = a;
6
    sort(b.begin(), b.end());
7
    map<int, int> mp;
8
    int prev = b[0], rnk = 0, n = a.size();
9
    for (int i = 0; i < n; i++) {
10
      if (b[i] != prev) {
11
        prev = b[i];
12
        rnk++;
13
      }
14
      mp[b[i]] = rnk;
15
    }
16
    for (int i = 0; i < n; i++) a[i] = mp[a[i]];
17
  }
18

19
  void update(int st[], int tind, int ind, int val, int tl, int tr) {
20
    if (tl > tr) return;
21
    if (tl == tr) {
22
      st[tind] = val;
23
      return;
24
    }
25
    int m = tl + (tr - tl) / 2, left = tind << 1;
26
    if (ind <= m)
27
      update(st, left, ind, val, tl, m);
28
    else
29
      update(st, left + 1, ind, val, m + 1, tr);
30
    st[tind] = max(st[left], st[left + 1]);
31
  }
32

33
  int query(int st[], int tind, int tl, int tr, int ql, int qr) {
34
    if (tl > tr or ql > tr or qr < tl) return 0;
35
    if (ql <= tl and tr <= qr) return st[tind];
36
    int m = tl + (tr - tl) / 2, left = tind << 1;
37
    return max(query(st, left, tl, m, ql, qr), query(st, left + 1, m + 1, tr, ql, qr));
38
  }
39

40
  vector<int> longestObstacleCourseAtEachPosition(vector<int> &a) {
41
    compress(a);
42
    int i, n = a.size();
43
    int st[4 * n + 10];
44
    memset(st, 0, sizeof(st));
45
    update(st, 1, a[0], 1, 0, n - 1);
46
    vector<int> dp(n);
47
    dp[0] = 1;
48

49
    for (i = 1; i < n; i++) {
50
      int mx = query(st, 1, 0, n - 1, 0, a[i]);
51
      dp[i] = 1 + mx;
52
      update(st, 1, a[i], dp[i], 0, n - 1);
53
    }
54

55
    return dp;
56
  }
57
};