Overview

For each of the \(N\) buses, we preprocess whether there are enough boxed lunches (\(S_i \geq P_i\)), and for \(M\) range queries, we efficiently determine “whether all buses within the range have enough boxed lunches.”

Analysis

Rephrasing the Problem

For each bus \(i\), if we compute the difference \(D_i = S_i - P_i\), then the condition for having enough boxed lunches \(S_i \geq P_i\) is equivalent to \(D_i \geq 0\).

The condition for rest plan \(j\) to be feasible is that all \(D_i\) within the range \([L_j, R_j]\) are non-negative, i.e.:

\[\min_{L_j \leq i \leq R_j} D_i \geq 0\]

In other words, this reduces to a Range Minimum Query problem.

Issues with the Naive Approach

If we scan the range \([L_j, R_j]\) for each query to find the minimum, each query takes \(O(N)\) in the worst case, resulting in \(O(NM)\) overall. Since both \(N\) and \(M\) can be up to \(2 \times 10^5\), this leads to a worst case of \(4 \times 10^{10}\) operations, resulting in TLE.

Solution

Using a Sparse Table, after \(O(N \log N)\) preprocessing, each query can be answered in \(O(1)\).

Algorithm

What is a Sparse Table?

A Sparse Table is a data structure that efficiently handles range minimum (or maximum) queries on a static array.

Preprocessing:

Define the table \(\text{sparse}[k][i]\) as “the minimum value in the range of length \(2^k\) starting at position \(i\).”

• \(k = 0\): \(\text{sparse}[0][i] = D_i\) (range of length \(1\))
• \(k \geq 1\): \(\text{sparse}[k][i] = \min(\text{sparse}[k-1][i],\ \text{sparse}[k-1][i + 2^{k-1}])\)

This splits a range of length \(2^k\) into a first half of length \(2^{k-1}\) and a second half of length \(2^{k-1}\), then combines them.

Query:

To find the minimum of the range \([L, R]\) (of length \(\ell = R - L + 1\)), let \(k = \lfloor \log_2 \ell \rfloor\):

\[\min(\text{sparse}[k][L],\ \text{sparse}[k][R - 2^k + 1])\]

This is a technique that covers the range with two intervals of length \(2^k\), allowing overlap. Since the \(\min\) operation returns the correct result even with overlap, the answer is obtained in \(O(1)\).

Concrete Example

When \(N = 5\), \(S = [5, 3, 4, 2, 6]\), \(P = [3, 4, 1, 2, 7]\):

\(D = [2, -1, 3, 0, -1]\)

Query \([1, 3]\) (1-indexed) → \(D_1, D_2, D_3 = 2, -1, 3\) → minimum is \(-1 < 0\) → No

Query \([3, 4]\) (1-indexed) → \(D_3, D_4 = 3, 0\) → minimum is \(0 \geq 0\) → Yes

Complexity

• Time complexity: \(O(N \log N + M)\) (\(O(N \log N)\) for preprocessing, \(O(1)\) per query)
• Space complexity: \(O(N \log N)\) (for storing the Sparse Table)

Implementation Notes

• 1-indexed → 0-indexed conversion: Since the input is 1-indexed, we convert with L -= 1, R -= 1 before accessing the Sparse Table.

• Precomputation of the logarithm table: Calling math.log2 for each query is slow, so we precompute a log_table array during preprocessing for speedup.

• Batch output: In Python, calling print \(M\) times is slow, so we accumulate results in a list and output them all at once using sys.stdout.write.

  Source Code

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    P = list(map(int, input().split()))
    
    # Sparse table for range minimum of (S_i - P_i)
    # If min(S_i - P_i) for i in [L, R] >= 0, then "Yes"
    diff = [S[i] - P[i] for i in range(N)]
    
    import math
    LOG = max(1, math.floor(math.log2(N)) + 1) if N > 0 else 1
    
    sparse = [None] * (LOG + 1)
    sparse[0] = diff[:]
    
    for k in range(1, LOG + 1):
        length = 1 << k
        sparse[k] = [0] * N
        for i in range(N - length + 1):
            sparse[k][i] = min(sparse[k-1][i], sparse[k-1][i + (1 << (k-1))])
    
    # Precompute log2
    log_table = [0] * (N + 1)
    for i in range(2, N + 1):
        log_table[i] = log_table[i // 2] + 1
    
    out = []
    for _ in range(M):
        L, R = map(int, input().split())
        L -= 1
        R -= 1
        length = R - L + 1
        k = log_table[length]
        min_val = min(sparse[k][L], sparse[k][R - (1 << k) + 1])
        out.append("Yes" if min_val >= 0 else "No")
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

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