Overview

This is a problem of finding the number of contiguous subsequences (intervals) from a positive integer sequence of length \(N\) such that the sum of elements is at most \(K\).

Analysis

1. Naive Approach

If we examine all interval combinations \((l, r)\), there are \(N(N+1)/2\) intervals. Since \(N = 2 \times 10^5\), the number of combinations is approximately \(2 \times 10^{10}\), which means a brute-force search cannot finish within the time limit (\(O(N^2)\) time complexity). A more efficient method is needed.

2. Utilizing Monotonicity

The key point of this problem is that every element \(A_i\) of the sequence is a positive integer. This gives us the following property (monotonicity): - If we fix the right endpoint of an interval and move the left endpoint to the right (shortening the interval), the sum always decreases. - If we fix the left endpoint of an interval and move the right endpoint to the right (lengthening the interval), the sum always increases.

Using this property, instead of examining all intervals independently, we can apply the Two Pointers technique to efficiently move the left and right endpoints while identifying the range that satisfies the condition.

Algorithm

Counting with the Two Pointers Technique

We manage “as we advance the right endpoint \(right\) one by one, how far to the right can we push the left endpoint \(left\) while keeping the sum within \(K\).”

1. Prepare a variable current_sum to hold the sum of the current interval.
2. Move the right endpoint \(right\) from \(0\) to \(N-1\) in order.
   • Add \(A_{right}\) to current_sum.
   • While current_sum exceeds \(K\), move the left endpoint \(left\) to the right and subtract \(A_{left}\) from current_sum.
3. At this point, if \(left\) is the minimum left endpoint that satisfies the condition when the right endpoint is \(right\), then the number of intervals with right endpoint \(right\) that satisfy the condition is the following \((right - left + 1)\):
   • \([left, right], [left+1, right], \ldots, [right, right]\)
4. By summing this count for each \(right\), we obtain the answer.

Concrete Example (\(N=4, K=10, A=\{3, 5, 4, 7\}\))

• \(right=0\): current_sum=3 (\(\leq 10\)). Count: \(0-0+1 = 1\) ({3})
• \(right=1\): current_sum=8 (\(\leq 10\)). Count: \(1-0+1 = 2\) ({3,5}, {5})
• \(right=2\): current_sum=12 (\(> 10\)). Advance \(left\).
  • Subtract \(A_0=3\) from current_sum \(\rightarrow\) 9 (\(\leq 10\)).
  • Count: \(2-1+1 = 2\) ({5,4}, {4})
• \(right=3\): current_sum=16 (\(> 10\)). Advance \(left\).
  • Subtract \(A_1=5\) \(\rightarrow\) 11 (\(> 10\))
  • Subtract \(A_2=4\) \(\rightarrow\) 7 (\(\leq 10\))
  • Count: \(3-3+1 = 1\) ({7})
• Total: \(1+2+2+1 = 6\)

Complexity

• Time Complexity: \(O(N)\)
  • The right endpoint \(right\) moves \(N\) times.
  • The left endpoint \(left\) also moves at most \(N\) times in total.
  • Therefore, the entire process completes in roughly the time it takes to scan the sequence twice.
• Space Complexity: \(O(N)\)
  • Memory is needed to store the sequence \(A\).

Implementation Notes

• Data type for sums: The total value \(K\) and the answer count can become very large, so depending on the programming language, you may need to use a 64-bit integer type (Python handles this natively).

• Fast I/O: Since \(N\) can be large, in Python you can reduce execution time by reading all input at once using sys.stdin.read().split() or similar methods.

  Source Code

import sys

def solve():
    # 入力の読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    a = list(map(int, input_data[2:]))
    
    ans = 0
    left = 0
    current_sum = 0
    
    # しゃくとり法（スライディングウィンドウ）を用いて条件を満たす区間を数え上げる
    for right in range(n):
        current_sum += a[right]
        
        # 合計が K を超える間、左端を右に動かす
        while current_sum > k and left <= right:
            current_sum -= a[left]
            left += 1
        
        # 現在の right を右端とする条件を満たす区間の数は (right - left + 1) 個
        ans += (right - left + 1)
        
    print(ans)

if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3-flash-preview.