Overview

This problem asks you to count the number of contiguous subarrays from a sequence of \(N\) positive integers where the sum of elements is at most \(K\). We solve this efficiently using the Two Pointers technique (sliding window).

Analysis

Naive Approach and Its Problems

If we try all intervals \((l, r)\), there are \(O(N^2)\) ways to choose intervals, and calculating the sum of each interval takes \(O(N)\), resulting in \(O(N^3)\) overall. Even using prefix sums gives \(O(N^2)\), which results in TLE for \(N = 2 \times 10^5\).

Key Insight: Monotonicity

This problem has the condition that all elements are positive. This gives us the following properties:

• Expanding an interval always increases the sum
• Shrinking an interval always decreases the sum

Using this monotonicity, we can apply the two pointers technique.

The Two Pointers Idea

When the right endpoint is fixed at \(r\), if we can find “the minimum left endpoint \(l\) such that the sum is at most \(K\)”, then any left endpoint from \(l, l+1, \ldots, r\) satisfies the condition (because shrinking the interval decreases the sum).

Furthermore, when we increase \(r\) by 1, the sum increases, so the new minimum left endpoint is at least as large as the previous one. In other words, the left endpoint only moves to the right, so we can process everything in \(O(N)\).

Algorithm

1. Initialize left endpoint left = 0, current interval sum current_sum = 0, answer count = 0
2. Move right endpoint right from \(0\) to \(N-1\) in order:
   • Add A[right] to current_sum
   • While current_sum > K, subtract A[left] and move left to the right
   • At this point, the sum of interval \([left, right]\) is at most \(K\)
   • The number of intervals with right endpoint right that satisfy the condition is right - left + 1
   • Add this count to count
3. Output count

Concrete Example (\(N=5, K=10, A=[3, 1, 4, 1, 5]\))

right	A[right]	current_sum	left	Number of valid intervals
0	3	3	0	1 ([3])
1	1	4	0	2 ([3,1], [1])
2	4	8	0	3 ([3,1,4], [1,4], [4])
3	1	9	0	4
4	5	14→10	1	4 ([1,4,1,5], etc.)

Answer: \(1+2+3+4+4 = 14\)

Complexity

• Time Complexity: \(O(N)\)
  • right advances \(N\) times, and left advances at most \(N\) times in total
• Space Complexity: \(O(N)\)
  • Required for storing array \(A\)

Implementation Notes

• By including the condition left <= right in the while loop, we correctly handle cases where all elements are greater than \(K\)
• current_sum and K can be up to approximately \(10^{14}\), so 64-bit integers are required (Python handles this automatically)
• Since all elements are positive, if current_sum <= K is satisfied, all intervals from left to right satisfy the condition

Source Code

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    count = 0
    current_sum = 0
    left = 0
    
    for right in range(N):
        current_sum += A[right]
        
        # While the sum exceeds K, move the left endpoint to the right
        while current_sum > K and left <= right:
            current_sum -= A[left]
            left += 1
        
        # For intervals from left to right, the sum is at most K
        # Here, all intervals with right endpoint at right and left endpoint at left, left+1, ..., right are at most K
        # (Since all elements are positive, shrinking the interval decreases the sum)
        if current_sum <= K:
            count += (right - left + 1)
    
    print(count)

solve()

---

This editorial was generated by claude4.5opus.