Overview

This is a problem where, for cars passing through intervals on a road that may contain damaged tiles, we need to determine whether the number of damaged tiles within each interval meets or exceeds a threshold.

Analysis

For each query (a car’s travel interval), we need to efficiently count the number of damaged tiles contained in the interval \([L_i, R_i]\). A naive approach would be to scan through all damaged tiles for each query, but since \(M\) and \(K\) can be up to \(2 \times 10^5\), the time complexity would be \(O(MK)\), requiring up to \(4 \times 10^{10}\) operations in the worst case. This cannot be processed within the time limit.

Instead, by pre-sorting the list of damaged tiles and using binary search, we can process each query in \(O(\log M)\). This reduces the overall time complexity to \(O(M \log M + K \log M)\).

Algorithm

1. Preprocessing: Sort the list of damaged tiles \(B\).
2. Query Processing: For each query \([L_i, R_i]\), perform the following steps:
   • Use bisect_left on the sorted list \(B\) to find the first position greater than or equal to \(L_i\) (lower bound).
   • Similarly, use bisect_right to find the first position greater than \(R_i\) (upper bound).
   • The difference between the upper and lower bound indices gives the number of damaged tiles contained in the interval \([L_i, R_i]\).
   • If this count is greater than or equal to \(T\), output YES; otherwise, output NO.

Complexity

• Time complexity: \(O(M \log M + K \log M)\)
  • Sorting takes \(O(M \log M)\), and binary search for each query takes \(O(\log M)\).
• Space complexity: \(O(M + K)\)
  • Memory is needed to store the list of damaged tiles \(B\) and the list of queries.

Implementation Notes

• All data is read from standard input at once to reduce I/O overhead.

• An iterator is used to process data sequentially, improving memory efficiency and speed.

• Python’s standard library bisect is utilized to achieve efficient binary search.

  Source Code

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

This editorial was generated by deepseekv3.