Overview

A problem where we determine how many books each student can borrow, based on grade-level restrictions.

Analysis

In this problem, for each student \(i\), we need to count the number of books \(j\) that satisfy the condition \(S_i \geq T_j\).

A naive approach would be to check all combinations of students and books (nested loops), but this would require up to \(2 \times 10^5 \times 2 \times 10^5 = 4 \times 10^{10}\) comparisons, which exceeds the time limit (TLE).

To handle this efficiently, we make the following observations: - The number of books each student can borrow equals “the count of \(T_j\) such that \(T_j \leq S_i\).” - Therefore, if the required grade list \(T\) for books is sorted, we can efficiently find “the largest index such that \(T_j \leq S_i\)” using binary search.

Specifically, for example, if
\(S_i = 5\),
\(T = [1, 2, 4, 6, 7]\)
then the key point is to find “the largest index where \(T_j \leq S_i\),” rather than the smallest \(T_j\) that is \(\geq S_i\).
In other words, by using bisect.bisect_right(T, s), we can obtain the first position greater than \(s\), and that index directly gives us the number of books the student can borrow.

In this way, by sorting \(T\) in advance, each query can be processed in \(O(\log M)\).

Algorithm

1. Read the input and sort the required grade list \(T\) for books.
2. For each student’s grade \(S_i\), use binary search on \(T\) to find the number of elements \(\leq S_i\).
   • Using Python’s bisect.bisect_right(T, s) returns the first index greater than \(s\), so it directly gives the number of books the student can borrow.
3. Output the results in order.

Complexity

• Time complexity: \(O(M \log M + N \log M)\)
  
  • \(O(M \log M)\) for sorting \(T\), and \(O(N \log M)\) for binary search per student
• Space complexity: \(O(N + M)\)
  
  • For arrays storing student and book information

Implementation Notes

• bisect.bisect_right returns “the first index greater than the specified value,” so it directly corresponds to the number of books that can be borrowed.

• Don’t forget to sort \(T\) first.

  Source Code

import bisect

# 入力受け取り
N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))

# Tをソート
T.sort()

# 各学生に対して、借りられる本の冊数を二分探索で求める
result = []
for s in S:
    # Tの中で s 以上となる最初の位置を二分探索で求める
    pos = bisect.bisect_right(T, s)
    result.append(pos)

# 結果出力
print(*result, sep='\n')

This editorial was generated by qwen3-coder-480b.