Overview

For each of \(N\) buses, determine whether “there are enough boxed lunches,” then efficiently determine whether there are zero buses with “insufficient boxed lunches” within each of the \(M\) given intervals \([L_j, R_j]\).

Analysis

1. Determining Each Bus Individually

First, whether each bus \(i\) is “distributable” or “not distributable” can be easily determined by comparing the given \(S_i\) and \(P_i\). - If \(S_i \geq P_i\), distribution is possible (OK) - If \(S_i < P_i\), distribution is not possible (NG)

2. Naive Approach

For each rest plan (query), one could check each bus from \(L_j\) to \(R_j\) one by one. However, this method requires up to \(N\) checks per query. Since there are \(M\) queries, the worst-case time complexity is \(O(N \times M)\). In this problem, \(N, M \leq 2 \times 10^5\), so the number of operations can reach up to \(4 \times 10^{10}\), which will not finish within the time limit.

3. Speeding Up with Prefix Sums

To efficiently determine “whether there is at least one NG bus within an interval,” we use the concept of prefix sums.

First, we convert the state of each bus into a numerical value: - For bus \(i\) that is not distributable (NG): \(A_i = 1\) - For bus \(i\) that is distributable (OK): \(A_i = 0\)

Then, checking whether there exists a non-distributable bus within an interval \([L, R]\) is equivalent to checking whether the sum of \(A_i\) within the interval is 1 or more.

To compute interval sums quickly, we precompute a prefix sum array \(pref\): - \(pref[k] = A_1 + A_2 + \dots + A_k\) (the total number of NG buses from the first through the \(k\)-th bus)

With this prepared, the number of NG buses in any interval \([L, R]\) can be computed in \(O(1)\) as follows: - Number of NG buses in the interval \(= pref[R] - pref[L-1]\)

If this value is \(0\), the plan is Yes (distribution possible); if it is \(1\) or more, the plan is No (distribution not possible).

Algorithm

1. For each bus \(i = 1, \dots, N\), determine whether \(S_i < P_i\).
2. Store the results as an array \(A\) of \(0\)s and \(1\)s, and construct its prefix sum array \(pref\).
3. For each query \((L_j, R_j)\), compute \(pref[R_j] - pref[L_j-1]\).
4. If the result is \(0\), output Yes; otherwise, output No.

Complexity

• Time Complexity: \(O(N + M)\)
  • Building the prefix sum takes \(O(N)\), and answering each query takes \(O(1)\), so the overall complexity is \(O(N + M)\), which is sufficiently fast.
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the input data and the prefix sum array.

Implementation Notes

• Fast I/O: In Python, when \(N, M\) are on the order of \(2 \times 10^5\), the standard input() may not be fast enough. It is effective to read all input at once using sys.stdin.read().split() or similar methods.

• Index Adjustment: The problem statement is 1-indexed (starting from 1), but program arrays are often 0-indexed (starting from 0), so care must be taken with the range specification of prefix sums (especially the left endpoint \(L-1\)).

  Source Code

import sys

def solve():
    # 競技プログラミングにおいて、入力を一度に読み込んで処理するのは高速化の一般的な手法です。
    # sys.stdin.read().split() は、すべての空白文字（スペース、改行など）で分割された文字列のリストを返します。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # すべての入力文字列を整数のリストに変換します。
    # これにより、インデックスによる高速なアクセスが可能になります。
    data = list(map(int, input_data))
    
    # バスの台数 N と休憩プランの数 M を取得します。
    N = data[0]
    M = data[1]
    
    # 弁当の数 S_i と生徒の人数 P_i のデータが始まる位置（オフセット）を設定します。
    # S_1, S_2, ..., S_N は data[2] から data[N+1] まで
    # P_1, P_2, ..., P_N は data[N+2] から data[2N+1] までに格納されています。
    s_offset = 2
    p_offset = 2 + N
    
    # 各バスにおいて弁当が足りない（S_i < P_i）かどうかを判定し、累積和を計算します。
    # pref[k] は、バス 1 からバス k までの間で弁当が不足しているバスの総数を表します。
    # これにより、任意の区間 [L, R] における不足バスの有無を O(1) で判定できます。
    pref = [0] * (N + 1)
    for i in range(N):
        # バス (i+1) が弁当不足（配布不可）かどうかをチェック
        if data[s_offset + i] < data[p_offset + i]:
            pref[i+1] = pref[i] + 1
        else:
            pref[i+1] = pref[i]
            
    # クエリ（休憩プラン）が始まる位置を設定します。
    query_start = 2 + 2 * N
    results = []
    
    # 各休憩プランについて判定を行います。
    for j in range(M):
        # L_j と R_j は 1-indexed で与えられます。
        L = data[query_start + 2 * j]
        R = data[query_start + 2 * j + 1]
        
        # 区間 [L, R] 内に弁当不足のバスが 1 台も存在しない場合、
        # pref[R] - pref[L-1] が 0 になります。
        if pref[R] - pref[L-1] == 0:
            results.append("Yes")
        else:
            results.append("No")
            
    # 判定結果を改行区切りで一括出力します。
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3-flash-thinking.