Overview

Given the training intensity over \(N\) days, count the number of intervals of \(K\) or more consecutive days whose total is at least \(M\).

Analysis

In this problem, for every interval \((l, r)\), we need to determine whether it has “length at least \(K\)” and “sum at least \(M\)”.

Naive Approach and Its Issues

The first idea that comes to mind is to try all possible intervals \((l, r)\). If we compute the sum from scratch for each interval, the time complexity becomes \(O(N^3)\), which is far too slow since \(N\) can be up to \(2 \times 10^5\).

For example, consider the following input:

N=5, K=2, M=5
A = [2, 2, 2, 2, 2]

In this case, intervals such as \((l,r)=(1,2), (1,3), ..., (4,5)\) are all candidates, but naively computing the sum for each one would take too much time.

Improvement: Prefix Sums and Binary Search

The standard technique for efficiently computing interval sums is prefix sums. By preparing a prefix sum array \(prefix\), the sum of any interval \([l, r]\) can be computed in \(O(1)\):

\[ \text{sum}(l, r) = prefix[r] - prefix[l-1] \]

Next, we need to efficiently count the “intervals that satisfy the conditions.” For a fixed left endpoint \(l\), if we can find the first right endpoint \(r\) where the interval sum becomes at least \(M\) as we increase \(r\), then all subsequent values of \(r\) will also satisfy the condition.

Specifically, for each \(l\), we perform the following operations: 1. Compute the first right endpoint that satisfies the minimum interval length \(K\): \(min\_r = l + K - 1\). 2. Within the range from this point to \(N\), use binary search to find the first \(r\) where the interval sum is at least \(M\). 3. If such an \(r\) exists, include everything from that point to the end in the count.

By doing this, we avoid recomputing the sum for each interval and also avoid brute-force enumeration, allowing us to find the answer efficiently.

Algorithm

1. Build the prefix sum array \(prefix\) (of length \(N+1\)).
2. For each left endpoint \(l = 1, 2, ..., N\), do the following:
   • Compute the first right endpoint satisfying the minimum interval length \(K\): \(min\_r = l + K - 1\).
   • If \(min\_r > N\), skip.
   • Use binary search to find the smallest right endpoint \(valid\_r\) where the interval sum is at least \(M\).
   • If such a \(valid\_r\) exists, all right endpoints from \(valid\_r\) to \(N\) satisfy the condition, so add \(N - valid\_r + 1\) to the count.

Complexity

• Time complexity: \(O(N \log N)\)
  • Binary search is performed for each \(l\), so the overall complexity is \(O(N \log N)\).
• Space complexity: \(O(N)\)
  • The prefix sum array has size \(N+1\).

Implementation Notes

• Adding \(0\) at the beginning of the prefix sum array simplifies index handling.

• In the binary search, since we are looking for “the first position that satisfies the condition,” we update with right = mid - 1.

• To safely reference prefix[l-1] even when \(l=1\), manage the prefix array with shifted indices.

  Source Code

import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    M = int(data[2])
    
    A = list(map(int, data[3:3+N]))
    
    # 累積和を計算
    prefix = [0] + list(accumulate(A))
    
    count = 0
    
    # 各開始位置 l について、条件を満たす終了位置 r の個数を数える
    for l in range(1, N+1):
        # 区間長が K 以上である最小の r
        min_r = l + K - 1
        if min_r > N:
            continue
        
        # 二分探索で条件を満たす最小の r を求める
        left = min_r
        right = N
        valid_r = -1
        
        while left <= right:
            mid = (left + right) // 2
            s = prefix[mid] - prefix[l-1]
            if s >= M:
                valid_r = mid
                right = mid - 1
            else:
                left = mid + 1
        
        # 条件を満たす r が存在すれば、それ以降すべての r も条件を満たす
        if valid_r != -1:
            count += N - valid_r + 1
            
    print(count)

if __name__ == "__main__":
    main()

---

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