Overview

Given \(N\) tiles, \(M\) of which are damaged, the problem asks us to determine whether each of the \(K\) given intervals \([L_i, R_i]\) contains \(T\) or more damaged tiles.

Analysis

Naive Approach

For each car, we could check each tile from \(L_i\) to \(R_i\) one by one and count the number of damaged tiles. However, in the worst case (e.g., when all cars travel from tile \(1\) to tile \(N\)), a single query takes \(O(N)\). The overall time complexity becomes \(O(K \times N)\), and given the constraints (\(N, K \leq 2 \times 10^5\)), this would require up to about \(4 \times 10^{10}\) operations, which exceeds the time limit.

Efficient Approach

The problem of “quickly computing the sum within a specific range” can be solved efficiently using a Prefix Sum. If we precompute “how many damaged tiles exist among the first \(i\) tiles from the left,” we can determine the number of damaged tiles in any interval \([L, R]\) in \(O(1)\).

Algorithm

We find the solution using the following steps:

1. Recording damage information: Prepare an array damaged of length \(N+1\). Set damaged[B_j] = 1 if tile \(B_j\) is damaged, and 0 otherwise.
2. Building the prefix sum: Create an array prefix_sum of length \(N+1\).
   • prefix_sum[0] = 0
   • prefix_sum[i] = prefix_sum[i-1] + damaged[i] (\(1 \leq i \leq N\)) This way, prefix_sum[i] represents the total number of damaged tiles from tile \(1\) to tile \(i\).
3. Processing queries: For each car (interval \([L, R]\)), the number of damaged tiles count can be computed as follows:
   • count = prefix_sum[R] - prefix_sum[L-1] If this count is greater than or equal to the threshold \(T\), output YES; otherwise, output NO.

Complexity

• Time complexity: \(O(N + M + K)\)
  • Recording damage information takes \(O(M)\), building the prefix sum takes \(O(N)\), and processing each query takes \(O(1)\) (totaling \(O(K)\)), so the entire process runs in linear time.
• Space complexity: \(O(N)\)
  • The arrays for storing tile information (damaged and prefix_sum) use \(O(N)\) memory.

Implementation Notes

• Fast I/O: Since \(N\) and \(K\) can be as large as \(2 \times 10^5\), in Python it is much faster to read all input at once using sys.stdin.read().split() and output all at once using sys.stdout.write(), rather than calling input() repeatedly.

• Index handling: Since tile numbers start from \(1\), we allocate the prefix sum array with size \(N+1\) and subtract prefix_sum[L-1] to correctly compute the sum over the interval \([L, R]\).

  Source Code

import sys

def solve():
    # 入力を一括で読み込み、高速化を図る
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    idx = 0
    N = int(input_data[idx])
    M = int(input_data[idx+1])
    K = int(input_data[idx+2])
    T = int(input_data[idx+3])
    idx += 4
    
    # 損傷したタイルの情報を取得
    damaged = [0] * (N + 1)
    for _ in range(M):
        b = int(input_data[idx])
        damaged[b] = 1
        idx += 1
        
    # 累積和を計算して、ある範囲内の損傷タイル数をO(1)で求められるようにする
    prefix_sum = [0] * (N + 1)
    for i in range(1, N + 1):
        prefix_sum[i] = prefix_sum[i-1] + damaged[i]
        
    # 各車のクエリを処理
    results = []
    for _ in range(K):
        L = int(input_data[idx])
        R = int(input_data[idx+1])
        idx += 2
        
        # [L, R] の範囲に含まれる損傷タイルの枚数
        count = prefix_sum[R] - prefix_sum[L-1]
        
        if count >= T:
            results.append("YES")
        else:
            results.append("NO")
            
    # 結果をまとめて出力
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-thinking.