Overview

Based on the quality scores of products and the threshold values of inspections, we determine the number of products discarded in each inspection.

Analysis

In this problem, we need to select and remove products with quality scores below the threshold from the “remaining products” through multiple inspections.

Issues with the Naive Approach

For example, if we check all products each time, verify which ones are still alive, and count up those below the threshold, the worst case requires \(O(NQ)\) operations. This means up to \(4 \times 10^{10}\) computations, resulting in TLE (Time Limit Exceeded).

Additionally, actually removing products from the list each time they are discarded is also costly.

Improvement Strategy

An important observation is that “the quality scores of products are fixed” and “only the threshold value changes with each inspection.”

Based on this, we use the following approach: - Sort and maintain the quality scores of products. - Manage a list current_scores containing only the “surviving scores.” - For each inspection, use binary search to efficiently determine “the number of elements below the threshold.” - Remove that many elements from the front of the list to prepare for the next inspection.

By doing this, each search takes \(O(\log N)\), and the total becomes approximately \(O(Q \log N)\).

Algorithm

1. Sort the list of product quality scores \(A\) to create sorted_A.
2. Initialize current_scores with sorted_A (assuming all products are alive).
3. For each inspection:
   • Receive the threshold value \(T_j\).
   • Use bisect.bisect_left(current_scores, T_j) to find the number of elements less than \(T_j\) (= the number of products to be discarded).
   • Add that count to the answer.
   • Remove that many elements from the front of current_scores (treating them as discarded).

Complexity

• Time complexity: \(O(N \log N + Q \log N)\)
  (\(O(N \log N)\) for the initial sort, \(O(\log N + k)\) for binary search and partial list deletion per query, but since deletions occur at most \(N\) times in total, this is acceptable in an amortized sense)
• Space complexity: \(O(N)\)

Implementation Notes

• bisect.bisect_left is very effective for returning “the number of elements less than a specified value” in a sorted list.

• del current_scores[:count] can remove elements from the front of a list in bulk, and this operation is performed relatively efficiently in Python.

• sys.stdin.read is used to read input quickly.

  Source Code

import bisect
import sys

input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    Q = int(data[1])
    A = list(map(int, data[2:N+2]))
    T = list(map(int, data[N+2:N+2+Q]))
    
    # 製品の品質スコアをソートしたリスト
    sorted_A = sorted(A)
    # 各要素がまだ存在しているかを管理するフラグリスト
    alive = [True] * N
    
    # 現在生きている製品の品質スコアを管理するリスト（ソートされた状態）
    current_scores = sorted_A[:]
    
    results = []
    
    for threshold in T:
        # 基準値未満の製品の数を二分探索で求める
        idx = bisect.bisect_left(current_scores, threshold)
        count = idx
        results.append(count)
        
        # 廃棄された製品をcurrent_scoresから削除
        # ここでは、current_scoresの最初のcount個を削除
        del current_scores[:count]
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

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