Overview

This problem asks us to count how many “contiguous subsequences” of a sequence of length \(N\) have a sum of \(K\) or more.

Analysis

1. Straightforward Approach (Brute Force)

First, let’s consider a method that examines all contiguous intervals \((l, r)\). Enumerating all pairs where \(1 \leq l \leq r \leq N\) gives approximately \(\frac{N^2}{2}\) combinations. Given the constraint \(N = 2 \times 10^5\), the number of intervals reaches about \(2 \times 10^{10}\), and computing the sum for each one individually would not fit within the time limit (resulting in TLE).

2. Key Property: Monotonicity

The crucial point of this problem is that “all sales values \(V_i\) are positive integers”. Due to this property, when the sum of an interval \([l, r]\) is \(K\) or more, extending the right endpoint further (\([l, r+1], [l, r+2], \dots, [l, N]\)) will also always have a sum of \(K\) or more.

In other words, for each left endpoint \(l\), if we can find “the smallest right endpoint \(r\) such that the sum is \(K\) or more”, then all \(r\) values to the right of it (a total of \(N - r + 1\)) satisfy the condition.

3. Efficient Solution

We utilize the property that “when the left endpoint \(l\) moves one position to the right, the smallest right endpoint \(r\) that satisfies the condition also moves to the right (or stays at the same position).” Using this, we can solve the problem efficiently with a technique called the “two-pointer method” (sliding window / caterpillar method).

Algorithm

Two-Pointer Method

We perform the counting with the following steps:

1. Move the left endpoint index left from \(0\) to \(N-1\).
2. For each left, while the current interval sum current_sum is less than \(K\), advance the right endpoint index right and add V[right] to the sum.
3. Once current_sum becomes \(K\) or more, add the number of stores from the current right to the end, (N - right + 1), to the answer.
   • Note: In the code, since right += 1 is performed after advancing right, the number to add is N - right + 1.
4. In preparation for the next left, subtract the current V[left] from current_sum.

Complexity

• Time Complexity: \(O(N)\)
  • The two pointers left and right each move at most \(N\) times. The total computation is on the order of traversing the sequence 1 to 2 times, making it very fast.
• Space Complexity: \(O(N)\)
  • Memory is needed to store the \(N\) sales data values in a list.

Implementation Notes

• Data type for the sum: \(K\) can be up to \(10^{14}\), and the total of sales can be even larger, so depending on the programming language, you may need to use a 64-bit integer type (in Python, this is handled automatically).

• Managing the right endpoint: It is efficient to control right so that it does not exceed \(N\) within the while loop, and to compute the remaining count all at once the moment the condition is satisfied.

• Comparison with prefix sums: Instead of the two-pointer method, it is also possible to solve this in \(O(N \log N)\) by computing prefix sums and then using binary search (bisect) to find the smallest \(r\) for each \(l\).

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 店舗数, K: 目標売上
    N = int(input_data[0])
    K = int(input_data[1])
    # V: 各店舗の売上リスト
    V = list(map(int, input_data[2:]))
    
    ans = 0
    right = 0
    current_sum = 0
    
    # しゃくとり法を用いて条件を満たす区間の個数を数える
    for left in range(N):
        # 合計が K 以上になるまで右端を進める
        while right < N and current_sum < K:
            current_sum += V[right]
            right += 1
            
        # 合計が K 以上になった場合
        # 現在の left に対して、right-1 以降のすべての右端 index が条件を満たす
        if current_sum >= K:
            ans += (N - right + 1)
            
        # 左端を一つ進める準備として、現在の left の値を合計から引く
        current_sum -= V[left]
        
    # 結果を出力
    print(ans)

if __name__ == '__main__':
    solve()

---

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