Overview

For each interval, count the number of damaged tiles and determine whether it meets or exceeds the threshold.

Discussion

In this problem, for each car’s travel interval \([L_i, R_i]\), we need to efficiently find how many damaged tiles are contained within it.

A naive approach would be to linearly scan the range \([L_i, R_i]\) each time to count the number of damaged tiles, but this requires \(O(N)\) computation per query, resulting in \(O(K \cdot N)\) in the worst case overall, which is too slow given the constraints (\(K, N \leq 2 \times 10^5\)).

Instead, by sorting the list of damaged tiles in advance and using binary search, we can efficiently determine the number of damaged tiles in each interval. Specifically, on the sorted list of damaged tiles, we find the number of elements contained in the interval \([L_i, R_i]\) as follows:

• The smallest index with value \(\geq L_i\): bisect_left
• The smallest index with value \(> R_i\) (i.e., the largest index with value \(\leq R_i\) plus 1): bisect_right

The difference between these two gives the number of damaged tiles in the interval.

For example, if the damaged tiles are [3, 7, 10, 15] and the interval is [5, 12]: - bisect_left(B, 5) → index 1 (element 7) - bisect_right(B, 12) → index 3 (position of element 15) - The difference is \(3 - 1 = 2\) → the interval contains 2 tiles: 7 and 10

With this method, each query can be answered in \(O(\log M)\).

Algorithm

1. Sort the list of damaged tiles \(B\).
2. For each car’s travel interval \([L_i, R_i]\), do the following:
   • Use bisect_left(B, L_i) to get the smallest index with value \(\geq L_i\).
   • Use bisect_right(B, R_i) to get the smallest index with value \(> R_i\) (i.e., the largest index with value \(\leq R_i\) plus 1).
   • The difference is the number of damaged tiles.
   • If the count is \(\geq T\), output YES; otherwise, output NO.

Complexity

• Time complexity: \(O(M \log M + K \log M)\)
  
  • \(O(M \log M)\) for sorting, and \(O(\log M)\) per query performed \(K\) times.
• Space complexity: \(O(M)\)
  
  • Space required to store the list of damaged tiles.

Implementation Notes

• The list of damaged tiles must be sorted in advance.

• Be careful about the distinction between bisect_left and bisect_right (they handle boundary conditions differently).

• In Python, the bisect module makes this straightforward to implement.

  Source Code

import bisect

# 入力読み込み
N, M, K, T = map(int, input().split())
B = list(map(int, input().split()))
B.sort()

# 各車について処理
for _ in range(K):
    L, R = map(int, input().split())
    # 損傷タイルの中で [L, R] に含まれる個数をカウント
    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")

This editorial was generated by qwen3-coder-480b.