Overview

For each student’s grade \(S_i\), the problem asks us to find “how many books satisfy the condition \(T_j \le S_i\)” for all students. We preprocess the required grade \(T\) of the books cleverly to count the number efficiently.

Analysis

The books that student \(i\) can borrow are all books satisfying the condition \(S_i \ge T_j\). In other words, for each student, we need to count “the number of \(T_j \le S_i\).”

A naive approach would check all books for each student: - \(N\) students × \(M\) books gives \(O(NM)\)

The constraints are \(N, M \le 2 \times 10^5\), so in the worst case this results in about \(4 \times 10^{10}\) comparisons, which won’t finish in time (TLE).

The key observation is as follows: - If we sort the required grades \(T_j\) in ascending order, then for a given grade \(s\), the books with “\(T_j \le s\)” are lined up consecutively from the beginning of the array. - Therefore, “how many elements are \(\le s\)” can be efficiently determined using binary search.

For example, if \(T = [1, 2, 2, 5, 7]\): - For \(s=2\), the elements \(\le 2\) are \([1,2,2]\), which is 3 - For \(s=6\), the elements \(\le 6\) are \([1,2,2,5]\), which is 4

In this way, by finding the boundary position (right end), we can determine the count.

Algorithm

1. Sort the required grade array \(T\) in ascending order.
2. For each student’s grade \(s = S_i\), use binary search to:
   • Find the number of elements in \(T\) that are \(\le s\).
3. Output that count.

In the implementation, we use bisect_right(T, s). This returns “the position where value s can be inserted on the right side in the sorted array T (= the number of elements \(\le s\)).” Therefore, the answer is simply bisect_right(T, s).

Complexity

• Time complexity: \(O(M \log M)\) for sorting, \(O(N \log M)\) for binary search over all students, totaling \(O(M \log M + N \log M)\)
• Space complexity: \(O(M)\) (to store the sorted \(T\); including output, it’s about \(O(N+M)\))

Implementation Tips

• By using bisect_right, we directly obtain “the number of \(T_j \le S_i\)” (note that bisect_left would give something closer to “the number of \(T_j < S_i\)”).

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

• Writing the output collectively with "\n".join(...) is also faster.

  Source Code

import sys
from bisect import bisect_right

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    S = data[2:2+N]
    T = data[2+N:2+N+M]

    T.sort()
    out = []
    for s in S:
        out.append(str(bisect_right(T, s)))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.