概要

道路の損傷タイルが含まれる区間を通過する車について、その区間に含まれる損傷タイルの数が閾値以上かどうかを判定する問題です。

考察

各クエリ（車の通行区間）に対して、区間 \([L_i, R_i]\) に含まれる損傷タイルの数を効率的に数える必要があります。素朴なアプローチとして、毎回全ての損傷タイルを走査して数える方法が考えられますが、\(M\) と \(K\) が最大で \(2 \times 10^5\) にもなるため、計算量が \(O(MK)\) となり、最悪 \(4 \times 10^{10}\) 回の操作が必要になってしまいます。これは制限時間内に処理できません。

そこで、損傷タイルのリストを事前にソートしておき、二分探索を用いることで、各クエリを \(O(\log M)\) で処理できます。これにより、全体の計算量を \(O(M \log M + K \log M)\) に抑えることができます。

アルゴリズム

1. 事前処理: 損傷タイルのリスト \(B\) をソートします。
2. クエリ処理: 各クエリ \([L_i, R_i]\) について以下の手順で処理します：
   • ソート済みリスト \(B\) に対して、\(L_i\) 以上の最初の位置（下限）を bisect_left で求めます。
   • 同様に、\(R_i\) より大きい最初の位置（上限）を bisect_right で求めます。
   • 上限と下限のインデックスの差が、区間 \([L_i, R_i]\) に含まれる損傷タイルの数になります。
   • この数が \(T\) 以上なら YES、そうでなければ NO を出力します。

計算量

• 時間計算量: \(O(M \log M + K \log M)\)
  • ソートに \(O(M \log M)\)、各クエリの二分探索に \(O(\log M)\) かかります。
• 空間計算量: \(O(M + K)\)
  • 損傷タイルのリスト \(B\) とクエリのリストを保持するためのメモリです。

実装のポイント

• 標準入力から一度に全てのデータを読み込むことで、入出力のオーバーヘッドを減らしています。

• イテレータを使用してデータを順次処理することで、メモリ効率と速度を向上させています。

• Python の標準ライブラリ bisect を利用して、効率的な二分探索を実現しています。

  ソースコード

import sys
import bisect

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    N = int(next(it)); M = int(next(it)); K = int(next(it)); T = int(next(it))
    B = [int(next(it)) for _ in range(M)]
    queries = []
    for i in range(K):
        L = int(next(it)); R = int(next(it))
        queries.append((L, R))
    
    B.sort()
    
    for L, R in queries:
        left_idx = bisect.bisect_left(B, L)
        right_idx = bisect.bisect_right(B, R)
        count = right_idx - left_idx
        if count >= T:
            print("YES")
        else:
            print("NO")

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。