Overview

Find the number of intervals where the total sales of consecutive stores is at least \(K\) yen.

Analysis

In this problem, we need to count the number of all pairs \((l, r)\) such that the sum of the interval \([l, r]\) is at least \(K\).

A naive approach would be to compute the sum for every interval, but this has a time complexity of \(O(N^3)\), or \(O(N^2)\) even with prefix sums, which is not feasible since \(N\) can be up to \(2 \times 10^5\) (TLE).

Therefore, we use a technique called the “two pointers” method.

Key Observation

• When fixing each right endpoint \(r\), if the left endpoint \(l\) satisfies a certain condition, then \(l' > l\) further to the right is also likely to satisfy the condition.
• In particular, since interval sums have monotonicity, we can determine whether the condition is satisfied while gradually moving the left endpoint.

An even more important point: - When the interval \([l, r]\) satisfies the condition, all intervals obtained by extending the right endpoint further (e.g., \([l, r+1], [l, r+2], \ldots, [l, N]\)) also satisfy the condition. - In other words, the number of intervals satisfying the condition with right endpoint at least \(r\) is \(N - r + 1\).

By leveraging this property, we can efficiently count using the two pointers method.

Algorithm

1. First, precompute prefix sums. This allows us to compute the sum of any interval in \(O(1)\).
   • prefix_sums[i] is \(V_1 + V_2 + \cdots + V_i\) (a 0 is prepended at the beginning for easier 0-indexed handling)
2. Move the right endpoint \(r\) from 1 to \(N\).
3. For each \(r\), find the minimum \(l\) such that the sum of the interval \([l, r]\) is at least \(K\).
4. If such an \(l\) is found, add the number of intervals satisfying the condition with right endpoint at least \(r\) (\(N - r + 1\)) to the answer.
5. Advance the left endpoint \(l\) and then examine the next right endpoint.

In this way, we efficiently find the total number of intervals satisfying the condition.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• By inserting 0 at the beginning of the prefix sums, the interval sum calculation becomes simpler.
• In the two pointers method, the left endpoint advances at most \(N\) times in total, so the entire process runs in linear time.
• The key part is count += N - right + 1, which adds the number of intervals satisfying the condition that include the current right endpoint.

## Source Code

```python
import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    V = list(map(int, data[2:]))
    
    # 累積和を計算
    prefix_sums = [0] + list(accumulate(V))
    
    count = 0
    # 尺取り法 (two pointers)
    left = 0
    for right in range(1, N + 1):
        # 区間 [left, right) の和が K 以上になるまで left を進める
        while prefix_sums[right] - prefix_sums[left] >= K:
            count += N - right + 1
            left += 1
            
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.