Overview

For each bus, we determine whether “the number of lunches is at least the number of students,” and for each query (rest plan), we efficiently check whether there exists at least one bus within the interval that does not satisfy this condition.

Analysis

Whether bus \(i\) can distribute lunches is determined simply by checking \(S_i \ge P_i\). The condition for a rest plan \((L, R)\) to allow distribution can be rephrased as:

• The interval \([L, R]\) contains no buses that are unable to distribute (\(S_i < P_i\)).

Naively scanning \(i=L..R\) for each query to check “is there any bus that cannot distribute” would be \(O(NM)\) in the worst case, which is far too slow for \(N, M \le 2\times 10^5\).

Therefore, we prepare a structure that can quickly count “the number of buses unable to distribute” over an interval. If the count of such buses in the interval is \(0\), the answer is Yes; if it is \(1\) or more, the answer is No.

Algorithm

1. For each bus, create an array \(bad[i]\) where \(bad[i] = 1\) if the bus cannot distribute and \(bad[i] = 0\) if it can (\(1 \le i \le N\)).
   • \(bad[i] = 1 \iff S_i < P_i\)
2. Build a prefix sum array \(pref\) (precomputation) of \(bad\):
   • \(pref[0]=0\)
   • \(pref[i] = pref[i-1] + bad[i]\)
3. For a query \((L, R)\), the number of buses unable to distribute in the interval \([L, R]\) is:
   • \(pref[R] - pref[L-1]\)
4. If this is \(0\), there are no buses unable to distribute in the interval, so the answer is Yes; otherwise, No.

Concrete Example

For instance, if \(bad = [0, 1, 0, 1, 0]\) (buses 2 and 4 cannot distribute), then: - The count of unable buses in \([1,3]\) is \(1\) (bus 2 exists) → No - The count of unable buses in \([3,3]\) is \(0\) → Yes

Complexity

• Time complexity: Precomputation is \(O(N)\), each query is \(O(1)\), so the total is \(O(N+M)\)
• Space complexity: \(O(N)\) for the prefix sum array, etc.

Implementation Notes

• The input uses \(1\)-indexed intervals \([L, R]\), but Python arrays are \(0\)-indexed. Making the prefix sum \(pref\) of length \(N+1\) and treating \(pref[i]\) as “the total for the first \(i\) buses” helps avoid mistakes.

• The interval sum is always computed as \(pref[R] - pref[L-1]\) (this works even when \(L=1\) since \(pref[0]\) is available).

• Output is optimized by collecting results and printing with "\n".join(...).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    P = list(map(int, input().split()))

    pref = [0] * (N + 1)
    for i in range(1, N + 1):
        bad = 1 if S[i - 1] < P[i - 1] else 0
        pref[i] = pref[i - 1] + bad

    out = []
    for _ in range(M):
        L, R = map(int, input().split())
        out.append("Yes" if pref[R] - pref[L - 1] == 0 else "No")

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.