Overview

This problem asks us to efficiently count the number of intervals \((l, r)\) where the total sales of consecutive stores is at least \(K\) yen, using prefix sums and binary search.

Analysis

Naive Approach and Its Issues

The first idea that comes to mind is to try all combinations of \((l, r)\) and compute the sum of each interval.

for l in 1 to N:
    for r in l to N:
        Compute the sum of interval [l, r] and compare with K

However, this method has approximately \(\frac{N^2}{2}\) combinations of \((l, r)\), and when \(N = 2 \times 10^5\), it requires about \(2 \times 10^{10}\) computations, resulting in TLE (Time Limit Exceeded).

Key Observations

1. Using prefix sums, we can compute interval sums in \(O(1)\)

   • Define \(\text{prefix}[i] = V_1 + V_2 + \cdots + V_{i}\)
   • Then \(V_l + V_{l+1} + \cdots + V_r = \text{prefix}[r] - \text{prefix}[l-1]\)

2. Since all \(V_i \geq 1\), the prefix sum array is strictly increasing

   • \(\text{prefix}[0] < \text{prefix}[1] < \text{prefix}[2] < \cdots < \text{prefix}[N]\)
   • On a monotonically increasing array, we can use binary search!

3. Reformulating the condition

   • \(V_l + \cdots + V_r \geq K\)
   • \(\Leftrightarrow \text{prefix}[r] - \text{prefix}[l-1] \geq K\)
   • \(\Leftrightarrow \text{prefix}[r] \geq \text{prefix}[l-1] + K\)

In other words, for each \(l\), if we use binary search to find “the smallest \(r\) such that \(\text{prefix}[r] \geq \text{prefix}[l-1] + K\)”, then all \(r\) from that value to \(N\) satisfy the condition.

Algorithm

1. Compute prefix sums

   • \(\text{prefix}[0] = 0\)
   • \(\text{prefix}[i] = \text{prefix}[i-1] + V_i\) (\(i = 1, 2, \ldots, N\))

2. Binary search for each \(l\)

   • Compute \(\text{target} = \text{prefix}[l-1] + K\)
   • Use binary search on the prefix sum array to find the smallest index \(m\) where the value is at least \(\text{target}\)
   • If \(m \leq N\) and \(m \geq l\), then \(r = m, m+1, \ldots, N\) gives \((N - m + 1)\) intervals that satisfy the condition

3. Sum up the counts for all \(l\)

Concrete Example

For \(N = 4\), \(K = 6\), \(V = [2, 3, 4, 1]\): - \(\text{prefix} = [0, 2, 5, 9, 10]\)

When \(l = 1\): - \(\text{target} = 0 + 6 = 6\) - The smallest \(r\) such that \(\text{prefix}[r] \geq 6\) is \(3\) (\(\text{prefix}[3] = 9\)) - \(r = 3, 4\) gives 2 valid intervals

Complexity

• Time complexity: \(O(N \log N)\)
  • Computing prefix sums takes \(O(N)\)
  • Binary search for each \(l\) takes \(O(N \log N)\)
• Space complexity: \(O(N)\)
  • Storing the prefix sum array takes \(O(N)\)

Implementation Notes

• Prefix sum index management: In the code, we use 0-indexed implementation, so prefix[i+1] = prefix[i] + V[i] with prefix[0] = 0. The sum of interval \([l, r]\) (0-indexed) is prefix[r+1] - prefix[l].

• Binary search boundary conditions: We need to verify that the index found by bisect_left is at least \(l+1\) (due to the constraint \(r \geq l\)).

• Overflow considerations: Since \(K\) can be up to \(10^{14}\), \(V_i\) up to \(10^9\), and \(N\) up to \(2 \times 10^5\), prefix sums can reach approximately \(2 \times 10^{14}\). In Python, there is no need to worry about integer overflow.

  Source Code

import bisect

def solve():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    
    # 累積和を計算
    # prefix[i] = V[0] + V[1] + ... + V[i-1]
    # prefix[0] = 0
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + V[i]
    
    # V[l] + V[l+1] + ... + V[r] = prefix[r+1] - prefix[l]
    # これが >= K となる条件は prefix[r+1] - prefix[l] >= K
    # つまり prefix[r+1] >= prefix[l] + K
    
    # すべてのV_iが正なので、prefixは単調増加
    # 各lに対して、prefix[r+1] >= prefix[l] + K となる最小のr+1を二分探索で見つける
    # そのようなr+1がm以上N+1以下であれば、(N+1) - m 個の組が条件を満たす
    
    count = 0
    for l in range(N):
        # prefix[l] + K 以上となる最小のインデックスを探す
        target = prefix[l] + K
        # bisect_leftで target 以上となる最初の位置を探す
        idx = bisect.bisect_left(prefix, target)
        
        # idx は l+1 以上 N+1 以下でなければならない（r >= l なので r+1 >= l+1）
        if idx <= N:
            # r+1 が idx から N までの範囲で条件を満たす
            # r は idx-1 から N-1 まで
            # ただし r >= l なので idx-1 >= l, つまり idx >= l+1
            start = max(idx, l + 1)
            if start <= N:
                count += N - start + 1
    
    print(count)

solve()

---

This editorial was generated by claude4.5opus.