Overview

This is a problem where we need to determine how many of \(M\) books each of \(N\) students can borrow. The condition for student \(i\) to borrow book \(j\) is “the student’s grade \(S_i \geq\) the required grade \(T_j\) of the book,” and we need to efficiently count the number of books satisfying this condition.

Analysis

Naive Approach (Brute Force)

For each student \(i\), we could check all books \(j\) and verify whether the condition \(S_i \geq T_j\) is satisfied. In this case, the time complexity is \(O(N \times M)\). Given the constraints of this problem where \(N, M \leq 2 \times 10^5\), this would require up to about \(4 \times 10^{10}\) operations, which will not fit within the time limit (typically around 2 seconds).

Efficient Approach (Binary Search)

When counting the number of \(T_j\) values satisfying \(S_i \geq T_j\), we can compute this efficiently by sorting the required grades \(T\) of the books in ascending order beforehand.

For example, if a student’s grade is \(S_i = 10\) and the required grades of books are sorted as \(T = [3, 5, 8, 12, 15]\), we can immediately see that there are 3 values at most 10: \([3, 5, 8]\). Binary Search can be used as a technique to quickly find “how many elements are less than or equal to a given value” in a sorted array.

Algorithm

1. Sort the list of required grades \(T\) in ascending order.
2. For each student \(i = 1, \dots, N\), perform the following:
   • Using binary search on the sorted \(T\), find the number of elements that are less than or equal to \(S_i\).
   • Specifically, use a function like Python’s bisect_right to find “the position (index) where the first element greater than \(S_i\) appears.” This index value directly equals “the number of elements less than or equal to \(S_i\).”
3. Output the result for each student in order.

Complexity

• Time Complexity: \(O((N + M) \log M)\)
  • Sorting the book list \(T\) takes \(O(M \log M)\).
  • Performing binary search for each student (\(N\) students) takes \(O(N \log M)\).
  • When \(N, M = 2 \times 10^5\), \((N+M) \log M\) is approximately \(4 \times 10^5 \times 18 \approx 7.2 \times 10^6\), which easily fits within the time limit.
• Space Complexity: \(O(N + M)\)
  • This is needed to store the input data (student grades and required book grades).

Implementation Notes

• Binary Search Library: In Python, you can easily implement binary search by using bisect_right from the bisect module.

• Fast I/O: Since \(N\) and \(M\) can be large, reading all input at once with sys.stdin.read().split() and writing output at once with sys.stdout.write() is faster than repeatedly calling input(), reducing execution time.

  Source Code

import sys
from bisect import bisect_right

def main():
    # 標準入力からすべてのデータを取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 学生の数, M: 本の数
    N = int(input_data[0])
    M = int(input_data[1])
    
    # S: 各学生の学年
    S = list(map(int, input_data[2:2+N]))
    # T: 各本を借りるために必要な最低学年
    T = list(map(int, input_data[2+N:2+N+M]))
    
    # 二分探索を行うために、本に必要な学年のリストをソートする
    T.sort()
    
    results = []
    for s_val in S:
        # bisect_right(T, s_val) は、Tの中で s_val 以下の要素の個数を返す
        count = bisect_right(T, s_val)
        results.append(str(count))
        
    # 結果をまとめて出力
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3-flash-preview.