Delivering Boxes from Storage to Ports LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<int> stree;
4
  void update(int tidx, int s, int e, int idx, int val) {
5
    if (s == e) {
6
      stree[tidx] = val;
7
      return;
8
    }
9
    int mid = (s + e) / 2;
10
    if (idx <= mid)
11
      update(2 * tidx, s, mid, idx, val);
12
    else
13
      update(2 * tidx + 1, mid + 1, e, idx, val);
14
    stree[tidx] = min(stree[2 * tidx], stree[2 * tidx + 1]);
15
  }
16
  int query(int tidx, int s, int e, int l, int r) {
17
    if (s > r or e < l)
18
      return INT_MAX;
19
    else if (s >= l and e <= r)
20
      return stree[tidx];
21
    int mid = (s + e) / 2;
22
    int left = query(2 * tidx, s, mid, l, r);
23
    int right = query(2 * tidx + 1, mid + 1, e, l, r);
24
    return min(left, right);
25
  }
26
  int boxDelivering(vector<vector<int>> &boxes, int port, int box, int weigh) {
27
    int n = boxes.size();
28
    vector<long long> trips(n + 1), pref(n);
29
    trips[0] = 0, pref[0] = boxes[0][1];
30
    for (int i = 1; i < n; i++) {
31
      pref[i] = pref[i - 1] + boxes[i][1];
32
      if (boxes[i][0] != boxes[i - 1][0]) {
33
        trips[i] = trips[i - 1] + 1;
34
      } else {
35
        trips[i] = trips[i - 1];
36
      }
37
    }
38
    trips[n] = trips[n - 1];
39
    vector<long long> dp(n);
40
    stree = vector<int>(4 * n + 1, INT_MAX);
41
    update(1, 0, n - 1, 0, 0);
42
    // dp[i] = dp[j] + (trips[i] - trips[j+1]) + 2
43
    for (int i = 0; i < n; i++) {
44
      // L nikalo ?
45
      int l = 0, r = i;
46
      while (l < r) {
47
        int mid = (l + r) / 2;
48
        long long tot = pref[i] - ((mid - 1 >= 0) ? pref[mid - 1] : 0);
49
        if (tot <= weigh and i - mid + 1 <= box) {
50
          r = mid;
51
        } else {
52
          l = mid + 1;
53
        }
54
      }
55
      int mini = query(1, 0, n, l, i);
56
      dp[i] = mini + trips[i] + 2;
57
      update(1, 0, n, i + 1, dp[i] - trips[i + 1]);
58
    }
59
    return dp[n - 1];
60
  }
61
};