Overview

Given \(N\) days of training intensity data, the problem asks to find the number of intervals \((l, r)\) that satisfy two conditions: “the interval length is at least \(K\) days” and “the total intensity is at least \(M\)”.

Analysis

Naive Approach and Its Limitations

Consider exhaustively searching all intervals \((l, r)\). There are approximately \(\frac{N^2}{2}\) ways to choose an interval, and computing the sum of each interval takes \(O(N)\) in the worst case, resulting in an overall time complexity of \(O(N^3)\). Using prefix sums reduces the sum computation to \(O(1)\), but the overall complexity is still \(O(N^2)\). In this problem, \(N = 2 \times 10^5\), so \(N^2 = 4 \times 10^{10}\), which will not finish within the time limit. A more efficient \(O(N)\) or \(O(N \log N)\) approach is needed.

Exploiting Monotonicity

The key observation in this problem is that “all training intensities \(A_i\) are positive (at least \(1\))”. This means that when the left endpoint \(l\) is fixed, the interval sum strictly increases as the right endpoint \(r\) moves to the right.

If a certain interval \([l, r]\) satisfies the conditions (sum \(\geq M\) and length \(\geq K\)), then all intervals obtained by extending the right endpoint — \([l, r+1], [l, r+2], \dots, [l, N]\) — also satisfy the conditions. Therefore, if we can efficiently find “the smallest \(r\) that satisfies the conditions” for each \(l\), then the number of valid intervals with left endpoint \(l\) can be computed at once as \((N - r + 1)\).

Algorithm

1. Building the Prefix Sum Array

To quickly compute the sum of an interval \([l, r]\), we prepare a prefix sum array \(S\). - \(S[0] = 0\) - \(S[i] = A_1 + A_2 + \cdots + A_i\) Using this, we can compute \(A_l + \cdots + A_r = S[r] - S[l-1]\).

2. Two-Pointer Technique (Sliding Window)

We move the left endpoint \(l\) from \(1\) onward, and correspondingly move the right endpoint candidate \(r\_ptr\). 1. Sum condition: Find the smallest \(r\) such that \(S[r] - S[l-1] \geq M\), i.e., \(S[r] \geq S[l-1] + M\), and call it \(r\_ptr\). Since \(A_i > 0\), as \(l\) increases, \(r\_ptr\) can only move to the right. 2. Length condition: For the interval length to be at least \(K\), we need \(r \geq l + K - 1\). 3. Combining conditions: The smallest right endpoint \(r_{start}\) satisfying both conditions is \(\max(r\_ptr, l + K - 1)\).

If \(r_{start} \leq N\), then all right endpoints \(r_{start}, r_{start}+1, \dots, N\) are valid choices, so we add \((N - r_{start} + 1)\) to the answer.

Complexity

• Time complexity: \(O(N)\)
  • Computing the prefix sums takes \(O(N)\).
  • In the two-pointer part, both the left endpoint \(l\) and the right endpoint \(r\_ptr\) move at most \(N\) times each, so it is \(O(N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the prefix sum array of length \(N+1\).

Implementation Notes

• Handling large values: The total value \(M\) can be as large as \(10^{14}\), so depending on the programming language, you need to use 64-bit integer types (in Python, the standard integer type is fine).

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

• Boundary conditions: The range of \(l\) goes up to \(N-K+1\), which is the last position where an interval of length at least \(K\) can be formed.

  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])
    M = int(input_data[2])
    # A_1, A_2, ..., A_N を 0-indexed のリストとして保持します。
    A = list(map(int, input_data[3:]))
    
    # 累積和の計算
    # S[i] は最初の i 日間の練習強度の合計 (A_1 + ... + A_i) を表します。
    # S[0] = 0 とします。
    S = [0] * (N + 1)
    current_sum = 0
    for i in range(N):
        current_sum += A[i]
        S[i+1] = current_sum
        
    ans = 0
    r_ptr = 1
    
    # 各開始日 l に対して、条件を満たす終了日 r の個数を数えます。
    # 連続する日数が K 以上である必要があるため、l は最大で N - K + 1 までとなります。
    for l in range(1, N - K + 2):
        # 目標とする累積和の値： S[r] - S[l-1] >= M  =>  S[r] >= S[l-1] + M
        target = S[l-1] + M
        
        # 練習強度の合計が M 以上になる最小の r を尺取り法（二つのポインタ）で探します。
        # A_i >= 1 より累積和 S は単調増加するため、r_ptr を戻す必要はありません。
        while r_ptr <= N and S[r_ptr] < target:
            r_ptr += 1
        
        # 条件1: 合計が M 以上 (r >= r_ptr)
        # 条件2: 期間の長さが K 以上 (r - l + 1 >= K  => r >= l + K - 1)
        # これら両方を満たす最小の r を求めます。
        actual_r_start = max(r_ptr, l + K - 1)
        
        # 最小の r が期間内 (N以下) であれば、それ以降のすべての r も条件を満たします。
        if actual_r_start <= N:
            # 終了日 r として選べるのは [actual_r_start, N] の範囲の整数です。
            ans += (N - actual_r_start + 1)
    
    # 結果の出力
    print(ans)

if __name__ == '__main__':
    solve()

---

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