Overview

This problem asks us to count the number of periods \((l, r)\) of \(K\) or more consecutive days where the total reading time does not exceed the time limit \(T\). We solve it efficiently by combining prefix sums with the two pointers technique.

Analysis

Naive Approach

Examining all pairs \((l, r)\) with a double loop yields \(O(N^2)\) pairs, which is too slow for \(N \leq 2 \times 10^6\).

Key Observation

Since \(A_i \geq 1\), the prefix sum \(\text{prefix}[i]\) is strictly monotonically increasing. This means that for a fixed \(l\), as \(r\) increases, the interval sum \(\text{prefix}[r] - \text{prefix}[l-1]\) monotonically increases.

Therefore, for each \(l\), the “maximum \(r\) that satisfies the condition” is uniquely determined. Furthermore, when \(l\) increases by \(1\), \(\text{prefix}[l-1]\) increases, so the subtracted amount becomes larger and the condition becomes more relaxed. Thus, the maximum valid \(r\) never decreases as \(l\) increases.

This monotonicity allows us to apply the two pointers technique.

Algorithm

1. Build prefix sums: Compute \(\text{prefix}[i] = A_1 + A_2 + \cdots + A_i\).

2. Reformulate the condition: The condition \(C \times (A_l + \cdots + A_r) \leq T\) is equivalent to \(\text{prefix}[r] - \text{prefix}[l-1] \leq \lfloor T / C \rfloor\) (since all values are positive integers). Let \(\text{max\_sum} = \lfloor T / C \rfloor\).

3. Two pointers: While managing the right pointer right, for each \(l = 1, 2, \ldots, N\), do the following:

   • Update right to \(\max(\text{right}, l + K - 1)\) (minimum \(K\) days constraint).
   • If right > N, there is no valid interval for this \(l\), so skip.
   • If the condition is not satisfied at the minimum valid \(r = l + K - 1\), skip.
   • Extend right to the right as long as the condition is satisfied.
   • The valid range of \(r\) is \([l+K-1, \text{right}]\), so add \(\text{right} - (l+K-1) + 1\) to the answer.

Concrete example: For \(N=5, K=2, C=1, T=10, A=[3,2,1,4,5]\): - \(l=1\): The maximum \(r\) with sum \(\leq 10\) is \(4\) (sum \(3+2+1+4=10\)). Valid range is \(r \in [2,4]\) → 3 intervals - \(l=2\): The maximum \(r\) is \(4\) (sum \(2+1+4=7\)). Valid range is \(r \in [3,4]\) → 2 intervals - \(l=3\): The maximum \(r\) is \(5\) (sum \(1+4+5=10\)). Valid range is \(r \in [4,5]\) → 2 intervals - \(l=4\): Sum \(4+5=9 \leq 10\). Valid range is \(r \in [5,5]\) → 1 interval

Total: 8 intervals

Complexity

• Time complexity: \(O(N)\) (with two pointers, right advances at most \(N\) times in total)
• Space complexity: \(O(N)\) (for the prefix sum array)

Implementation Notes

• Overflow prevention: The product of \(C\) and the total page count can become large, but by transforming the condition to \(\text{prefix}[r] - \text{prefix}[l-1] \leq \lfloor T/C \rfloor\), we avoid large multiplications.

• Initialization of right: We do not reset right when \(l\) increases (exploiting monotonicity). However, if right < l + K - 1, we need to raise it to \(l + K - 1\).

• Fast input: Since \(N\) can be as large as \(2 \times 10^6\), we use sys.stdin.buffer.read() for bulk reading.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    C = int(input_data[1])
    T = int(input_data[2])
    K = int(input_data[3])
    A = [int(input_data[4 + i]) for i in range(N)]
    
    # prefix sum
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]
    
    # We need to count pairs (l, r) with 1 <= l <= r <= N, r - l + 1 >= K,
    # and C * (prefix[r] - prefix[l-1]) <= T
    # i.e., prefix[r] - prefix[l-1] <= T // C (integer division, but careful with floor)
    
    # Since A_i >= 1, the sum is monotonically increasing as r increases for fixed l.
    # We can use two pointers / sliding window approach.
    
    # For each l, find the maximum r such that C * (prefix[r] - prefix[l-1]) <= T
    # and r >= l + K - 1
    # The sum prefix[r] - prefix[l-1] is increasing in r.
    
    # threshold for sum: S <= T / C
    # Since all values are integers, S <= floor(T / C)
    max_sum = T // C
    
    count = 0
    # Two pointer: for each l (1-indexed), find max r such that prefix[r] - prefix[l-1] <= max_sum
    # Then valid r range is [l+K-1, max_r] if l+K-1 <= max_r
    
    right = 0  # right will track the furthest r (1-indexed) we can go
    # Actually, let's use a simpler two-pointer where we iterate l from 1 to N
    
    for l in range(1, N + 1):
        # We need prefix[r] - prefix[l-1] <= max_sum
        # Start right from max(right, l+K-1 - 1) ... but we need to be careful
        # Actually since prefix is non-decreasing (A_i >= 1), as l increases,
        # the maximum valid r can only increase or stay (since prefix[l-1] increases).
        # Wait, no: as l increases, prefix[l-1] increases, so the constraint becomes easier,
        # meaning max valid r can increase. But we also need r >= l+K-1 which increases.
        
        # Let's just find max r for each l using the pointer that only moves forward.
        if right < l + K - 1:
            right = l + K - 1
        
        if right > N:
            # No valid r for this l
            continue
        
        # Check if even the minimum valid r is feasible
        if prefix[right] - prefix[l - 1] > max_sum:
            continue
        
        # Expand right as far as possible
        while right + 1 <= N and prefix[right + 1] - prefix[l - 1] <= max_sum:
            right += 1
        
        # Valid r: from l+K-1 to right
        count += right - (l + K - 1) + 1
    
    print(count)

main()

This editorial was generated by claude4.6opus-thinking.