Overview

For each query, we determine whether the total cost of the specified interval \([L, R]\) exceeds the budget limit \(T\). We use prefix sums to efficiently compute the sum over many intervals.

Analysis

What we need for each shopping trip is the interval sum \(A_L + A_{L+1} + \cdots + A_R\).
If we naively sum from \(L\) to \(R\) each time, a single query takes \(O(N)\) in the worst case, resulting in \(O(NQ)\) overall. Given the constraints \(N, Q \le 2 \times 10^5\), the worst case involves approximately \(4 \times 10^{10}\) additions, which will not finish in time (TLE).

The key insight here is that interval sums can be computed in one step using prefix sums.
If we prepare the prefix sum \(pref[i] = A_1 + A_2 + \cdots + A_i\), then:

• The sum of the interval \([L, R]\) is
  \(pref[R] - pref[L-1]\)

This allows each query to be answered in \(O(1)\).

Example: When \(A = [3, 1, 4, 1, 5]\),
\(pref = [0, 3, 4, 8, 9, 14]\) (with \(pref[0]=0\) placed at the beginning)
The sum of the interval \([2,4]\) is \(pref[4]-pref[1]=9-3=6\).

Algorithm

1. Prepare an array \(pref\) of length \(N+1\) and set \(pref[0]=0\).
2. For \(i=1\) through \(N\), compute \(pref[i] = pref[i-1] + A_i\) (prefix sums).
3. For each query \((L, R)\):
   • Compute \(total = pref[R] - pref[L-1]\)
   • Output Yes if \(total > T\), otherwise output No

Complexity

• Time complexity: Preprocessing is \(O(N)\), each query is \(O(1)\), so the total is \(O(N+Q)\)
• Space complexity: \(O(N)\) for the prefix sum array

Implementation Notes

• By setting \(pref[0]=0\), we can use the same formula \(pref[R]-pref[L-1]\) even when \(L=1\), which simplifies the code.

• The total cost and \(T\) can be on the order of \(10^{14}\), so depending on the language, 64-bit integers are required (Python handles arbitrarily large integers natively).

• Since the number of queries can be large, collecting the output strings in an array and printing them all at once at the end is faster.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, Q, T = map(int, input().split())
    A = list(map(int, input().split()))
    pref = [0] * (N + 1)
    s = 0
    for i, x in enumerate(A, 1):
        s += x
        pref[i] = s

    out_lines = []
    for _ in range(Q):
        L, R = map(int, input().split())
        total = pref[R] - pref[L - 1]
        out_lines.append("Yes" if total > T else "No")
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.