Overview

Given a sequence of positive integers \(A\), count the number of contiguous subarrays (of length \(1\) or more) whose sum is at most \(K\).
Since \(N\) can be up to \(2 \times 10^5\), we need to count efficiently rather than examining all subarrays.

Analysis

Key Observation

• Since \(A_i \ge 1\) (all positive), extending an interval to the right always increases the interval sum.
• Due to this property, “for a given left endpoint \(l\), the maximum right endpoint \(r\) satisfying the condition (interval sum \(\le K\))” moves monotonically (when \(l\) increases by 1, the optimal \(r\) never moves back to the left).

Why the Naive Approach Fails

• Enumerating all intervals \((l, r)\) and computing their sums results in \(O(N^2)\) intervals (up to approximately \(2 \times 10^{10}\)), which exceeds the time limit.
• Even if we use prefix sums to compute each interval sum in \(O(1)\), the enumeration itself is \(O(N^2)\), resulting in TLE.

How to Solve It

By using the two pointers (sliding window) technique — “it looks like a double loop, but the right pointer never moves back” — we can count everything in \(O(N)\) total.

Algorithm

We maintain two pointers \(l, r\) and the sum \(s\) of the current interval \([l, r)\) (right endpoint exclusive).

1. Initial state: \(r = 0, s = 0, ans = 0\)
2. For each \(l = 0, 1, \dots, N-1\), do the following:
   • Extend the right endpoint \(r\) as far as possible:
     While \(r < N\) and \(s + A[r] \le K\),
     \(s \leftarrow s + A[r]\), \(r \leftarrow r + 1\)
   • At this point, the intervals with left endpoint \(l\) that satisfy the condition are [ [l,l], [l,l+1], \dots, [l,r-1] ] totaling \(r-l\) intervals, so \(ans \leftarrow ans + (r-l)\)
   • To advance to the next \(l\), remove \(A[l]\) from the interval:
     • However, if \(r == l\) (the interval is empty, e.g., adding \(A[l]\) alone would exceed \(K\)), the pointer would get stuck, so in that case, set \(r \leftarrow r+1\) to forcibly advance.
     • Otherwise, \(s \leftarrow s - A[l]\)

Concrete Example

Example: \(A = [2,1,3],\ K=3\) - \(l=0\): \([2]\) (OK), \([2,1]\) (OK), \([2,1,3]\) (NG) → \(r=2\) so add \(2\) - \(l=1\): Trying to extend from current \(r=2\), \(1+3=4\) is NG → only \([1]\), so \(1\) - \(l=2\): \([3]\) (OK) → \(1\)
Total: \(2+1+1=4\)

Complexity

• Time complexity: \(O(N)\)
  (Since \(r\) increases at most \(N\) times in total, the algorithm is linear even including the while loop)
• Space complexity: \(O(1)\)
  (Only a constant number of variables besides the input array)

Implementation Notes

• The “right pointer never moves back” monotonicity of the two pointers technique holds precisely because \(A_i\) is positive (it breaks down if negative numbers are present).

• The meaning of ans += r - l is “the number of valid intervals with left endpoint \(l\) fixed.”

• if r == l: r += 1 is a crucial operation to prevent an infinite loop when no interval satisfying the condition can be formed.

• Since \(K\) can be up to \(10^{14}\), the interval sum \(s\) requires 64-bit integers (not an issue in Python).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    r = 0
    s = 0
    ans = 0

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

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.