Overview

This problem requires checking whether each bus satisfies the lunch box distribution condition, and for each break plan, determining whether all buses within a specified contiguous range of buses satisfy the condition.

Analysis

For each break plan, we need to check whether \(S_i \geq P_i\) holds for all buses in the interval \([L_j, R_j]\). A naive approach that checks all buses in the interval for each query would have a worst-case time complexity of \(O(N \times M)\). Since both \(N\) and \(M\) can be up to \(2 \times 10^5\), this would require up to \(4 \times 10^{10}\) operations, which would not fit within the time limit.

Instead, we create an array where each bus is represented as 1 if it does not satisfy the condition (\(S_i < P_i\)) and 0 if it does. By efficiently finding whether the maximum value in an interval is 0 or 1, we can process each query quickly.

Algorithm

1. For each bus \(i\), create an array arr with elements set to 1 if \(S_i < P_i\), and 0 otherwise.
2. Build a segment tree (capable of handling range maximum queries).
3. For each break plan \(j\), retrieve the maximum value in the interval \([L_j-1, R_j)\) using the segment tree.
   • If the maximum is 0: all buses in the interval satisfy the condition, so output “Yes”
   • If the maximum is 1: there exists a bus that does not satisfy the condition, so output “No”

By using a segment tree, each query can be processed in \(O(\log N)\).

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • Building the segment tree takes \(O(N)\), and processing each query takes \(O(\log N)\)
• Space complexity: \(O(N)\)
  • The segment tree requires \(O(N)\) space

Implementation Notes

• The segment tree size is adjusted to a power of two so that it can be implemented as a complete binary tree.

• For query processing, the standard segment tree traversal method (bottom-up) is used to efficiently find the maximum value in an interval.

• sys.stdin.read is used for input reading to improve performance.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    S = [int(next(it)) for _ in range(n)]
    P = [int(next(it)) for _ in range(n)]
    
    # 各バスについて、条件を満たすかどうか（S_i >= P_i）を0/1で表現
    # 条件を満たさない（S_i < P_i）場合は1、満たす場合は0
    arr = [0] * n
    for i in range(n):
        if S[i] < P[i]:
            arr[i] = 1
    
    # セグメント木（区間の最大値または合計を求める）を構築
    # ここでは区間に1が存在するかどうか（最大値が1か）を確認すれば十分
    size = 1
    while size < n:
        size <<= 1
    seg = [0] * (2 * size)
    
    # セグ木の構築
    for i in range(n):
        seg[size + i] = arr[i]
    for i in range(size - 1, 0, -1):
        seg[i] = max(seg[2*i], seg[2*i+1])
    
    def query(l, r):
        l += size
        r += size
        res = 0
        while l < r:
            if l & 1:
                res = max(res, seg[l])
                l += 1
            if r & 1:
                r -= 1
                res = max(res, seg[r])
            l //= 2
            r //= 2
        return res
    
    output_lines = []
    for _ in range(m):
        l = int(next(it)) - 1
        r = int(next(it))
        max_val = query(l, r)
        if max_val == 0:
            output_lines.append("Yes")
        else:
            output_lines.append("No")
    
    print("\n".join(output_lines))

if __name__ == "__main__":
    main()

---

This editorial was generated by deepseekv3.