713. Stretches Whose Score Stays Under k
The SCORE of a stretch is its total multiplied by its length. Count the contiguous stretches
whose score is strictly less than k.
2 1 4 3 5, k = 10 -> 6
1 1 1, k = 5 -> 5
5 5 5, k = 6 -> 3
1, k = 1 -> 0
## The score grows faster than the window
Widening a window raises BOTH factors: the total rises because the values are positive, and the length rises by definition. So the score is strictly increasing in the window, and shrinking from the left strictly lowers it.
That is the monotonicity a window needs, and it is worth noticing that it holds for a product just as it does for a sum. Problem 708 leans on the same fact with a harder cost.
## Count by right end
s += a[hi]
while lo <= hi and s * (hi - lo + 1) >= k: s -= a[lo]; lo += 1
count += hi - lo + 1
Once the window lo .. hi is legal, every shorter window ending at hi is legal too, because
shortening lowers both factors. So all hi - lo + 1 of them count, and each stretch is
counted at its own single right end.
## Strictly less than, not at most
1 with k = 1 scores 1 * 1 = 1, which is not less than 1, so the answer is 0. Writing
<= k gives 1. That single test separates the two readings and is the reason it is in the
sample set.
## The lo <= hi guard
A single value whose own score reaches k empties the window. Without the guard the left
pointer overtakes the right and the count goes negative.
## Overflow
The score is a total up to 2 * 10^9 times a length up to 2 * 10^5, which is
4 * 10^14, and k itself can be 10^15. The COUNT reaches 2 * 10^10. Both need
64 bits, for different reasons.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ k ≤ 10^15` - `1 ≤ each value ≤ 10^4`
Input
The first line contains two integers n and k.
The second line contains n positive integers.
Output
Print one integer, the number of stretches scoring less than k.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.