Overview

This problem asks us to find the number of intervals \((l, r)\) such that the sum of the contiguous subsequence from the given sequence is at least \(K\).

Analysis

A naive approach would be to enumerate all intervals \((l, r)\), compute the sum of each interval, and check whether it is at least \(K\). However, the time complexity of this method is \(O(N^2)\), and since \(N\) can be as large as \(2 \times 10^5\), it will not fit within the time limit.

Therefore, we use the sliding window method (also known as the two-pointer technique) as an efficient solution. In this approach, for a fixed right endpoint \(r\), we find the minimum left endpoint \(l\) that satisfies the condition, and exploit the fact that all intervals from that \(l\) to \(r\) satisfy the condition.

Algorithm

1. Initialize the left endpoint \(l\) and the current interval sum \(total\) to \(0\).
2. Move the right endpoint \(r\) from \(0\) to \(N-1\) in order.
3. For each \(r\), add \(V[r]\) to \(total\).
4. While \(total \geq K\), repeat the following:
   • The current interval \([l, r]\) satisfies the condition, so when \(l\) is fixed, the intervals satisfying the condition are \([l, r], [l, r+1], ..., [l, N-1]\), which is \(N - r\) intervals.
   • Add \(N - r\) to \(count\).
   • Subtract \(V[l]\) from \(total\) and increment \(l\) by \(1\) (shrink the window from the left).
5. Output \(count\) as the final result.

In this algorithm, each element is processed at most \(2\) times (once when added as the right endpoint and once when removed as the left endpoint), so it operates efficiently.

Complexity

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

Implementation Notes

• The sliding window method uses \(2\) pointers: the left endpoint \(l\) and the right endpoint \(r\).

• When an interval satisfying the condition is found, we exploit the fact that all intervals from that left endpoint \(l\) to the end satisfy the condition, counting them all at once.

• By including \(left \leq right\) in the \(while\) loop condition, we prevent indices from going out of bounds.

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    K = int(data[1])
    V = list(map(int, data[2:2+n]))
    
    total = 0
    left = 0
    count = 0
    
    for right in range(n):
        total += V[right]
        while total >= K and left <= right:
            count += n - right
            total -= V[left]
            left += 1
            
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.