Overview

Given product quality scores \(A_i\), when each inspection discards all “not yet discarded” products with scores below the threshold \(T_j\), find the number of products newly discarded at each inspection.

Analysis

If we scan all “remaining products” at each inspection to check the condition, the worst case is \(O(NQ)\), which is too slow for \(2\times 10^5\).

The two key observations are:

1. Discarded products form a contiguous prefix when sorted by score
   At any point, if the threshold is \(x\), the discarded products are “all products with scores less than \(x\)” (when sorted, this corresponds to the first several elements from the beginning).

2. A threshold smaller than a previous one has no effect
   For example, if we previously inspected with \(T=10\) and discarded all products with scores \(<10\), then if \(T=5\) comes next, nothing additional is discarded.
   In other words, the only thing that matters is the running maximum of thresholds \(cur=\max(T_1,\dots,T_j)\).

Therefore, we just need to maintain “the total number of products discarded so far” and only compute the additional amount when the threshold is updated (increased).

Algorithm

1. Sort array \(A\) in ascending order.
2. Initialize variables:
   • \(cur\): the maximum effective threshold so far (initial value \(-1\))
   • \(removed\): the number of products discarded so far (initial value \(0\))
3. For each inspection, read threshold \(t\):
   • If \(t \le cur\), no additional discarding occurs, so the answer is 0.
   • Otherwise, use bisect_left(A, t) on the sorted \(A\) (the position where \(t\) or greater first appears).
     This represents “the number of products with scores less than \(t\)” \(= new\_removed\).
     • The number of products newly discarded this time is \(new\_removed - removed\).
     • Update \(removed \leftarrow new\_removed,\ cur \leftarrow t\).

Concrete Example

Sorting \(A=[3,1,8,6,2]\) gives \([1,2,3,6,8]\).

• \(t=4\): products with score \(<4\) are 3 items (1,2,3), so newly discarded is \(3-0=3\)
• \(t=7\): products with score \(<7\) are 4 items (1,2,3,6), so newly discarded is \(4-3=1\)
• \(t=5\): \(5 \le 7(=cur)\), so newly discarded is 0

Complexity

• Time complexity: \(O(N\log N)\) for sorting, plus \(O(\log N)\) per inspection for binary search, giving a total of \(O(N\log N + Q\log N)\)
• Space complexity: \(O(N)\) for the sorted array, etc.

Implementation Notes

• bisect_left(A, t) directly returns “the number of elements less than \(t\)”, so we output the difference new_removed - removed (outputting the cumulative total would be incorrect).

• When the threshold decreases, the result is always 0, so we maintain cur (the maximum threshold so far) and check t <= cur.

• Since the input can be large, reading all at once with sys.stdin.buffer.read() is faster.

  Source Code

import sys
from bisect import bisect_left

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)
    A = [next(it) for _ in range(N)]
    A.sort()

    cur = -1
    removed = 0
    out = []

    for _ in range(Q):
        t = next(it)
        if t <= cur:
            out.append("0")
        else:
            new_removed = bisect_left(A, t)
            out.append(str(new_removed - removed))
            removed = new_removed
            cur = t

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.