Overview

Given information about boxed lunches and students for each bus, the problem asks us to determine, for each of multiple rest plans, whether there are enough boxed lunches on every bus within the specified range.

Analysis

First, each rest plan asks: “Does \(S_i \geq P_i\) hold for all buses from bus \(L_j\) to \(R_j\)?” In other words, the question is: “Are all buses within the range in a state where there are enough boxed lunches?”

What about the naive approach?

The most straightforward method is, for each query, to check \(S_i \geq P_i\) for all buses in the range \([L_j, R_j]\). However, in the worst case, each query requires up to \(N\) comparisons, leading to a total of up to \(M \times N\) computations. Given the constraints \(N, M \sim 2 \times 10^5\), this amounts to up to \(4 \times 10^{10}\) operations, which clearly won’t fit within the time limit (TLE).

Improvement Idea

This is where “preprocessing + prefix sums” comes in.
For each bus \(i\), we precompute whether that bus has enough boxed lunches (\(S_i \geq P_i\)) and record it as True/False. Then, we just need to count the number of True values within the range.

By using “prefix sums,” we can efficiently compute the number of True values within a range.

For example, define the array ok as follows: - ok[i] = (S[i] >= P[i])

Then, precompute the prefix sum acc[i] as “the number of True values from ok[0] to ok[i-1].” The number of True values in any range [L, R] can then be computed as: - Number of True values in range [L, R] = acc[R+1] - acc[L]

This way, each query can be answered in constant time.

Algorithm

1. For each bus \(i\), determine whether S[i] >= P[i] and create a boolean list ok.
2. Build the prefix sum array acc from ok.
3. For each query \([L_j, R_j]\), compute the number of True values in the range using acc[R+1] - acc[L].
4. If that number equals the length of the range, all buses have enough boxed lunches, so output Yes; otherwise, output No.

Concrete Example

For example, suppose we have the following input:

N = 4, M = 2
S = [3, 2, 5, 1]
P = [2, 3, 4, 1]
Queries: [1, 3], [2, 4]

• ok = [True, False, True, True]
• acc = [0, 1, 1, 2, 3]
• Query 1: [1,3] → acc[4] - acc[1] = 3 - 1 = 2, range length = 3 → No
• Query 2: [2,4] → acc[5] - acc[2] = 3 - 1 = 2, range length = 3 → No

Complexity

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

Implementation Notes

• Use sys.stdin.read() for fast input reading.

• After creating the ok array, build the prefix sum based on it.

• Don’t forget to convert query indices to 0-indexed.

• Determine the answer by checking whether the number of True values in the range equals the range length.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    S = list(map(int, data[2:2+N]))
    P = list(map(int, data[2+N:2+2*N]))
    
    # 判定用配列: ok[i] = (S[i] >= P[i]) なら True
    ok = [S[i] >= P[i] for i in range(N)]
    
    # 累積和: acc[i] = ok[0] から ok[i-1] までのTrueの数
    acc = [0] * (N + 1)
    for i in range(N):
        acc[i+1] = acc[i] + (1 if ok[i] else 0)
    
    # クエリ処理
    results = []
    idx = 2 + 2*N
    for _ in range(M):
        L = int(data[idx]) - 1   # 0-indexed
        R = int(data[idx+1]) - 1 # 0-indexed
        count_true = acc[R+1] - acc[L]
        length = R - L + 1
        if count_true == length:
            results.append("Yes")
        else:
            results.append("No")
        idx += 2
    
    print("\n".join(results))

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.