Overview

For a positive integer sequence \(A\), we efficiently count the number of contiguous subarrays \((l,r)\) that have “length at least \(K\)” and “subarray sum at least \(M\)” using the two-pointer (sliding window) technique.

Analysis

Key Observation

• Since \(A_i \ge 1\), extending the right endpoint \(r\) to the right always increases the subarray sum.
• When fixing a left endpoint \(l\), let \(r^\*\) be the smallest right endpoint that first satisfies the conditions (length \(\ge K\) and sum \(\ge M\)). Then:
  • All subarrays \([l,r]\) with \(r \ge r^\*\) also satisfy the conditions (because extending to the right never decreases the sum).
  • Therefore, the contribution to the answer for left endpoint \(l\) is \(N - r^\* + 1\) subarrays.

Why a Naive Solution Doesn’t Work

If we try all pairs \((l,r)\) and compute the subarray sum, there are \(O(N^2)\) subarrays.
Since \(N \le 2\times 10^5\), \(O(N^2)\) is far too slow.

How to Solve It

We use the two-pointer technique, “advancing the left endpoint \(l\) by 1 at a time while advancing the right endpoint \(r\) only as much as needed.” - \(r\) never moves back to the left (monotonically increasing) - Therefore, the total number of moves of \(r\) is at most \(N\), allowing us to count everything in \(O(N)\).

Algorithm

We manage subarrays as half-open intervals \([l, r)\) (including \(l\), excluding \(r\)). Let \(s\) denote the subarray sum.

1. Initialization: \(l=0, r=0, s=0, ans=0\)
2. Move the left endpoint \(l\) from \(0\) to \(N-1\):
   1. First, extend the right endpoint until “length is at least \(K\)”
      
      • while \(r < N\) and \(r-l < K\): \(s += A[r]\), \(r += 1\)
      • If the length is still insufficient (\(r-l < K\)), then it’s impossible for any subsequent \(l\), so terminate
   2. Next, extend the right endpoint until “sum is at least \(M\)”
      
      • while \(r < N\) and \(s < M\): \(s += A[r]\), \(r += 1\)
   3. If \(s \ge M\), then the smallest right endpoint satisfying the condition is the current \(r\) (though since we use \([l, r)\), the actual rightmost element is \(r-1\))
      
      • At this point, all subarrays extended further to the right also satisfy the condition, so the count is \(N - (r-1)\)
      • Therefore, ans += N - r + 1
   4. If \(s < M\) still holds when \(r == N\), we can’t extend further to the right, so terminate (for subsequent \(l\) values, the sum only gets smaller, so it’s impossible)
   5. To prepare for the next \(l\), remove the left endpoint element \(A[l]\) from the subarray: \(s -= A[l]\)

Concrete Example (Illustration)

For example, when \(N=5, K=2\), if for some \(l\) the minimum achieving right endpoint is \(r^\*=4\) (1-indexed \(r^\*=4\)), then: - \((l,4), (l,5)\) — 2 subarrays achieve the condition - This can be computed at once as \(N - r^\* + 1 = 5 - 4 + 1 = 2\).

Complexity

• Time complexity: \(O(N)\)
  (The right endpoint \(r\) increases at most \(N\) times in total)
• Space complexity: \(O(1)\)
  (Only a constant number of variables besides the input array)

Implementation Notes

• Managing subarrays as \([l,r)\) (half-open intervals) is convenient since the length is simply \(r-l\).

• Pay attention to the meaning of ans += N - r + 1:
  The current subarray is \([l,r)\), and the smallest “position of the last element” satisfying the condition is \(r-1\).
  Since we can choose up to position \(N-1\), the count is \(N-(r-1)=N-r+1\).

• If \(s < M\) still holds when \(r==N\), achievement is impossible for all subsequent \(l\) values as well, so we can break (justified by the monotonicity from \(A_i>0\)).

  Source Code

import sys

def main():
    it = list(map(int, sys.stdin.buffer.read().split()))
    N, K, M = it[0], it[1], it[2]
    A = it[3:]

    ans = 0
    r = 0
    s = 0

    for l in range(N):
        if r < l:
            r = l
            s = 0

        while r < N and r - l < K:
            s += A[r]
            r += 1
        if r - l < K:
            break

        while r < N and s < M:
            s += A[r]
            r += 1

        if s >= M:
            ans += N - r + 1
        else:
            break

        s -= A[l]

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.