Count Subarrays With Score Less Than K LeetCode solution in C++

1
class Solution {
2
 public:
3
  typedef long long ll;
4
  long long countSubarrays(vector<int> &nums, long long k) {
5
    int n = nums.size();
6
    vector<ll> v(n + 1, 0);
7
    for (int i = 1; i <= n; i++) {
8
      v[i] += v[i - 1] + nums[i - 1];
9
      // doing prefix sum.
10
    }
11
    ll ans = 0;
12
    for (int i = 1; i <= n; i++) {
13
      int low = i;
14
      int high = n;
15
      int ans1 = -1;
16
      // counting the number of sub arrays in which the current element is
17
      // included by doing binary search. The current element is the starting
18
      // element of the subarrays we count.
19
      while (low <= high) {
20
        int mid = low + (high - low) / 2;
21
        ll sum = v[mid] - v[i - 1];
22
        sum *= (mid - i + 1);
23
        if (sum >= k) {
24
          high = mid - 1;
25
        } else {
26
          ans1 = mid;
27
          low = mid + 1;
28
        }
29
      }
30
      if (ans1 != -1) {
31
        ans += (ans1 - i + 1);
32
      }
33
    }
34
    return ans;
35
  }
36
};