概要

各バスの弁当と生徒の情報をもとに、複数の休憩プランそれぞれについて、その区間に含まれるすべてのバスで弁当が足りるかどうかを判定する問題です。

考察

まず、各休憩プランは「バス \(L_j\) から \(R_j\) までの区間すべてで \(S_i \geq P_i\) が成り立つか」を問うています。これは言い換えると、「区間内すべてのバスが『弁当が足りている』状態であるか」という質問になります。

素朴な方法では？

一番素直な方法は、各クエリごとに区間 \([L_j, R_j]\) 内のすべてのバスに対して \(S_i \geq P_i\) をチェックすることです。しかし、これだと最悪の場合、各クエリで最大 \(N\) 回の比較が必要になり、全体で最大 \(M \times N\) 回の計算が必要になります。制約が \(N, M \sim 2 \times 10^5\) なので、これは最大 \(4 \times 10^{10}\) 回となり、明らかに時間内に収まりません（TLE）。

改善のアイデア

そこで登場するのが「前処理＋累積和」です。
各バス \(i\) に対して、あらかじめ「そのバスで弁当が足りているか（\(S_i \geq P_i\)）」を True/False で記録しておきます。そして、この True の個数を区間内で数えられればよいわけです。

ここで「累積和」を使うことで、区間内の True の個数を高速に求めることができます。

例えば、配列 ok を以下のように定義します： - ok[i] = (S[i] >= P[i])

そして、acc[i] を「ok[0] から ok[i-1] までの True の数」として累積和を前計算しておけば、任意の区間 [L, R] における True の個数は次のように求められます： - 区間 [L, R] の True の個数 = acc[R+1] - acc[L]

こうすることで、各クエリへの応答が定数時間でできるようになります。

アルゴリズム

1. 各バス \(i\) について、S[i] >= P[i] を判定し、真偽値のリスト ok を作成する。
2. ok の累積和配列 acc を構築する。
3. 各クエリ \([L_j, R_j]\) について、区間内の True の数を acc[R+1] - acc[L] で求める。
4. その数が区間の長さに等しければ、すべてのバスで弁当が足りているので Yes、そうでなければ No を出力する。

具体例

例えば、以下のような入力があったとします：

N = 4, M = 2
S = [3, 2, 5, 1]
P = [2, 3, 4, 1]
クエリ: [1, 3], [2, 4]

• ok = [True, False, True, True]
• acc = [0, 1, 1, 2, 3]
• クエリ1: [1,3] → acc[4] - acc[1] = 3 - 1 = 2, 区間長=3 → No
• クエリ2: [2,4] → acc[5] - acc[2] = 3 - 1 = 2, 区間長=3 → No

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 入力を高速に読み込むために sys.stdin.read() を使用。

• ok 配列を作った後、それを元に累積和を構築。

• クエリのインデックスを 0-indexed に変換することを忘れない。

• 区間の True の個数が区間長と一致するかどうかで判定。

  ソースコード

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()

---

この解説は qwen3-coder-480b によって生成されました。