Overview

Given an array of product quality scores, each inspection discards products below a threshold value. The problem asks how many products are discarded at each inspection. The key point is that once a product is discarded, it is never discarded again.

Analysis

Key Insight: Only the “maximum so far” of threshold values matters

At each inspection, “products that have not yet been discarded and whose quality score is less than \(T_j\)” are discarded. Here, products with quality scores below any previous threshold \(T\) have already been discarded in past inspections.

In other words, if \(M\) is the maximum of all threshold values applied in inspections so far, then the products still remaining are only those with quality scores of \(M\) or higher.

• If the new threshold \(T_j\) is \(M\) or less: All products with quality scores below \(T_j\) have already been discarded in past inspections, so the number of discards is \(0\).
• If the new threshold \(T_j\) is greater than \(M\): Products with quality scores at least \(M\) and less than \(T_j\) are newly discarded.

Problem with the Naive Approach

Scanning all products each time to check whether they are below the threshold results in \(O(NQ)\) time complexity in the worst case, which causes TLE when \(N, Q\) are up to \(2 \times 10^5\).

Solution: Sorting + Binary Search

By sorting the quality scores in advance, we can find “the number of products with scores at least \(M\) and less than \(T_j\)” in \(O(\log N)\) using binary search.

Algorithm

1. Sort the quality score array \(A\) in ascending order.
2. Initialize the maximum threshold so far \(M\) to \(0\) (since quality scores are at least \(1\), nothing is discarded initially).
3. For each inspection \(j\):
   • If \(T_j > M\): Use binary search on the sorted array to find the number of elements at least \(M\) and less than \(T_j\). Specifically, the number of discards is bisect_left(A, T_j) - bisect_left(A, M). Update \(M\) to \(T_j\).
   • If \(T_j \leq M\): The number of discards is \(0\).

Concrete Example: \(A = [2, 5, 3, 1, 4]\), inspection thresholds are \(3, 2, 5\)

• After sorting: \(A = [1, 2, 3, 4, 5]\), \(M = 0\)
• Inspection 1 (\(T=3\)): At least \(0\) and less than \(3\) → \([1, 2]\), \(2\) products discarded. \(M = 3\)
• Inspection 2 (\(T=2\)): \(T \leq M\), so \(0\) products
• Inspection 3 (\(T=5\)): At least \(3\) and less than \(5\) → \([3, 4]\), \(2\) products discarded. \(M = 5\)

Complexity

• Time complexity: \(O(N \log N + Q \log N)\)
  • \(O(N \log N)\) for sorting, \(O(\log N)\) per inspection × \(Q\) inspections
• Space complexity: \(O(N + Q)\)
  • For the sorted array and storing results

Implementation Notes

• By initializing \(M\) to \(0\), the algorithm works correctly from the very first inspection (since quality scores are at least \(1\)).

• bisect_left(A, T) returns “the number of elements in \(A\) less than \(T\)”, so the number of elements in the interval \([M, T)\) is exactly bisect_left(A, T) - bisect_left(A, M).

• Output is batched using sys.stdout.write to speed up I/O in Python.

  Source Code

import bisect
import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    
    max_threshold = 0
    results = []
    
    for _ in range(Q):
        T = int(input())
        prev = max_threshold
        if T > max_threshold:
            # Count elements with prev <= A[i] < T
            left = bisect.bisect_left(A, prev)
            right = bisect.bisect_left(A, T)
            results.append(right - left)
            max_threshold = T
        else:
            results.append(0)
    
    sys.stdout.write('\n'.join(map(str, results)) + '\n')

main()

---

This editorial was generated by claude4.6opus-thinking.