Overview

You are given quality scores for \(N\) products, and \(Q\) inspections are performed, each with the operation “discard products with scores below threshold \(T_j\).” For each inspection, determine the number of products newly discarded at that point.

Analysis

Naive Approach and Its Limitations

One approach is to check all non-discarded products against the threshold for each inspection. However, since both the number of products \(N\) and the number of inspections \(Q\) can be up to \(2 \times 10^5\), this method (with complexity \(O(N \times Q)\)) would require up to about \(4 \times 10^{10}\) operations, which would not fit within the time limit.

Key Insight: The Order of Products Doesn’t Matter

Whether a product is discarded depends solely on its “quality score”—the original index (ordering) of the product is irrelevant. Additionally, once a product is discarded, it never reappears. Therefore, sorting and managing products in ascending order of quality score allows for efficient processing.

For example, suppose the scores are \([10, 2, 5, 8]\). Sorting in ascending order gives \([2, 5, 8, 10]\). 1. With threshold \(T_1 = 6\), scores \(2\) and \(5\) are discarded (2 products). The remaining products are \([8, 10]\). 2. With threshold \(T_2 = 4\), everything below \(6\) has already been discarded, so 0 new products are discarded. 3. With threshold \(T_3 = 9\), among the remaining products, score \(8\) (which is below \(9\)) is discarded.

In this way, by sorting the scores, we can quickly find “how far the products below the current threshold \(T_j\) extend” using binary search.

Algorithm

1. Sort: Sort all product quality scores \(A_1, \dots, A_N\) in ascending order.
2. Pointer Management: Initialize an index current_idx pointing to “the smallest product not yet discarded” to 0.
3. Processing Each Inspection: For each threshold \(T_j\) where \(j = 1\) to \(Q\), do the following:
   • Use binary search (the bisect_left function in Python) on the sorted list \(A\) to find the first position new_idx where the value is at least \(T_j\).
   • By setting the left boundary of the search range to current_idx, we can ignore already-discarded products.
   • The number of newly discarded products is new_idx - current_idx.
   • Update current_idx to new_idx in preparation for the next inspection.

Complexity

• Time Complexity: \(O(N \log N + Q \log N)\)
  • The initial sort takes \(O(N \log N)\).
  • Binary search is performed for each query, so the total for all queries is \(O(Q \log N)\).
  • Since \(N, Q \leq 2 \times 10^5\), this complexity is sufficiently fast.
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used for the array holding the product scores.

Implementation Notes

• Fast I/O: Since \(N\) and \(Q\) can be large, in Python it is faster to read all input at once using sys.stdin.read().split() rather than calling input() repeatedly.

• Using Binary Search: By utilizing the standard library’s bisect module, binary search can be implemented concisely and efficiently.

• Cumulative Processing: By progressively updating current_idx, the condition “never count a discarded product again” is naturally satisfied.

  Source Code

import sys
from bisect import bisect_left

def solve():
    # 標準入力からすべての入力を一括で読み込み、空白文字で分割してトークン化します。
    # これにより、大量の入力を高速に処理できます。
    tokens = sys.stdin.read().split()
    if not tokens:
        return
    
    # N: 製品の個数, Q: 品質検査の回数
    N = int(tokens[0])
    Q = int(tokens[1])
    
    # 各製品の品質スコアを取得し、昇順にソートします。
    # ソートしておくことで、二分探索を用いて効率的に廃棄対象を特定できます。
    A = list(map(int, tokens[2:2+N]))
    A.sort()
    
    # 品質検査の基準値 T_j をリストとして取得します。
    T = list(map(int, tokens[2+N:2+N+Q]))
    
    # current_idx は、まだ廃棄されていない製品のうち、
    # ソートされた品質スコアリスト A における最小のインデックスを指します。
    current_idx = 0
    results = []
    
    # 各検査について順番に処理を行います。
    for threshold in T:
        # bisect_left を使用して、品質スコアが threshold 以上である最初のインデックスを探します。
        # lo=current_idx を指定することで、すでに廃棄された製品を探索範囲から除外します。
        new_idx = bisect_left(A, threshold, lo=current_idx)
        
        # 以前の検査で廃棄されず、今回の検査で新たに廃棄される製品の個数は、
        # (今回の基準値未満の最初のインデックス) - (前回までの検査で廃棄された最後のインデックス) となります。
        discarded_count = new_idx - current_idx
        results.append(str(discarded_count))
        
        # 廃棄された製品の分、current_idx を進めます。
        current_idx = new_idx
        
    # すべての検査結果を改行で結合し、一括で出力します。
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

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