Overview

Given an array storing quality scores of products, perform multiple quality inspections (discarding products below a threshold value) and determine the number of products discarded in each inspection.

Analysis

A naive approach would be to check all products for each inspection and discard those below the threshold. However, since the number of products \(N\) and the number of inspections \(Q\) can each be up to \(2 \times 10^5\), the worst case results in \(O(N \times Q)\) time complexity, which cannot be processed within the time limit.

To solve this efficiently, the following observations are important: 1. Once the products are sorted, products below the threshold are always concentrated at the beginning of the array 2. Since the discarding process is cumulative, if we remember the previous discard position, the next inspection only needs to search from that position onward 3. By using binary search, we can quickly find the boundary of products below threshold \(T_j\)

Algorithm

1. Sort the product quality score array \(A\) in ascending order
2. Initialize a pointer ptr representing the starting position of currently valid products to 0
3. For each inspection \(j\):
   • Use binary search to find the first position idx where the value is at least \(T_j\)
   • The number of products from ptr to idx (idx - ptr) is the number discarded in this inspection
   • Update the pointer ptr to idx to prepare for the next inspection
4. Output the number of discarded products for each inspection sequentially

Complexity

• Time complexity: \(O(N \log N + Q \log N)\)
  • \(O(N \log N)\) for sorting
  • \(O(\log N)\) for binary search in each inspection, totaling \(O(Q \log N)\)
• Space complexity: \(O(N)\)
  • Memory required for storing the product array

Implementation Notes

• Use the bisect_left function to efficiently find the first position at or above the threshold

• Manage the starting position of remaining products using the pointer ptr

• Correctly handle cases where the number of discarded products in an inspection is 0

• Process input efficiently using bulk reading

  Source Code

import sys
import bisect

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    q = int(data[1])
    A = list(map(int, data[2:2+n]))
    T_list = list(map(int, data[2+n:2+n+q]))
    
    A.sort()
    count = n
    removed = 0
    ptr = 0
    
    for T in T_list:
        idx = bisect.bisect_left(A, T)
        to_remove = idx - ptr
        if to_remove > 0:
            ptr += to_remove
            removed = to_remove
        else:
            removed = 0
        print(removed)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.