Overview

For an array \(V\) where all elements are positive, count the number of contiguous subarray intervals \((l,r)\) whose sum is at least \(K\).

Analysis

If we brute-force all interval sums by extending \(r\) for each \(l\), the time complexity is \(O(N^2)\), which is too slow for \(N \le 2\times 10^5\).

The key observation here is that \(V_i \ge 1\) (all elements are positive).
Due to this property, as we move the right endpoint \(r\) to the right, the interval sum \(V_l+\cdots+V_r\) monotonically increases. Therefore:

• For a fixed left endpoint \(l\), once we find the “smallest right endpoint where the sum becomes at least \(K\)”,
• all intervals extending further to the right also satisfy the condition.

For example, if for some \(l\) the smallest right endpoint is \(r\) (i.e., \([l,r]\) is the first interval with sum \(\ge K\)), then \([l,r],[l,r+1],\dots,[l,N]\) all satisfy the condition, giving a count of \(N-r+1\).

This “smallest right endpoint” never moves far back to the left when we advance to \(l+1\) (since all values are positive, the required length doesn’t suddenly decrease). By maintaining the right endpoint as a single pointer that only moves forward, the entire process runs in \(O(N)\).

Algorithm

We use the Two Pointers / Sliding Window technique.

• The right pointer r represents a half-open interval \([l,r)\),
• and s holds the current interval sum.

Procedure: 1. Initialize l=0, r=0, s=0. 2. For each l, while s < K, move r to the right by performing s += V[r] (as long as r < N). 3. If s >= K, then extending the right endpoint further only increases the sum, so the number of valid intervals is
\(N - (r-1)\)
However, since r in the code represents the “next position to add” (half-open interval), we add N - r + 1 to the answer. 4. To advance to the next l, remove the left element by s -= V[l].

Since r increases at most \(N\) times in total, the algorithm runs efficiently.

Complexity

• Time complexity: \(O(N)\) (both l and r move at most \(N\) times each)
• Space complexity: \(O(1)\) (only constants beyond the input array)

Implementation Notes

• Managing with half-open intervals \([l,r)\) makes the logic for advancing r and computing counts cleaner (this is why the code uses ans += N - r + 1).

• Once s >= K is reached, all intervals with right endpoints beyond that point satisfy the condition, so they can be counted all at once.

• \(K\) and the interval sums can be as large as \(10^{14}\), but Python’s int supports arbitrary precision, so this is safe.

  Source Code

import sys

def main():
    it = map(int, sys.stdin.buffer.read().split())
    N = next(it)
    K = next(it)
    A = [next(it) for _ in range(N)]

    r = 0
    s = 0
    ans = 0

    for l in range(N):
        while r < N and s < K:
            s += A[r]
            r += 1
        if s >= K:
            ans += N - r + 1
        s -= A[l]

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.