Overview

This problem asks us to efficiently determine, for each student’s grade level \(S_i\), the number of books they can borrow (books satisfying \(T_j \leq S_i\)). We solve this by combining sorting with binary search.

Analysis

The Essence of the Problem

The condition for student \(i\) to borrow book \(j\) is \(S_i \geq T_j\). In other words, for each student, we need to count “how many books have a required grade level at or below their own grade level.”

Naive Approach and Its Issues

The simplest method is to check all books for each student:

for i in range(N):
    count = 0
    for j in range(M):
        if S[i] >= T[j]:
            count += 1
    print(count)

This method has time complexity \(O(N \times M)\). When \(N, M\) are at most \(2 \times 10^5\), this requires up to \(4 \times 10^{10}\) operations in the worst case, resulting in TLE (Time Limit Exceeded).

Solution Idea

We want to quickly find “the count of \(T_j\) values that are at most \(S_i\).”

Key insight: If we sort array \(T\) in advance, elements satisfying \(T_j \leq S_i\) will be consecutive from the beginning of the array.

For example, sorting \(T = [3, 1, 4, 2]\) gives \(T = [1, 2, 3, 4]\). - When \(S_i = 2\), those satisfying \(T_j \leq 2\) are \([1, 2]\) — 2 books - When \(S_i = 3\), those satisfying \(T_j \leq 3\) are \([1, 2, 3]\) — 3 books

Finding “how many elements are at most \(S_i\)” can be done in \(O(\log M)\) using binary search.

Algorithm

1. Sort the array \(T\) of required grade levels in ascending order
2. For each student \(i\):
   • Use binary search on the sorted \(T\) to find the count of elements at most \(S_i\)
   • bisect_right(T, S[i]) returns “the index of the first element in \(T\) greater than \(S_i\)”
   • This equals “the count of elements at most \(S_i\)”

Concrete Example

For \(N=3, M=4\), \(S = [2, 4, 1]\), \(T = [3, 1, 4, 2]\):

1. Sort \(T\) → \(T = [1, 2, 3, 4]\)
2. Student 1 (\(S_1 = 2\)): bisect_right([1,2,3,4], 2) = 2 → 2 books
3. Student 2 (\(S_2 = 4\)): bisect_right([1,2,3,4], 4) = 4 → 4 books
4. Student 3 (\(S_3 = 1\)): bisect_right([1,2,3,4], 1) = 1 → 1 book

Complexity

• Time complexity: \(O(M \log M + N \log M)\)
  • Sorting \(T\) takes \(O(M \log M)\)
  • Binary search for each student is \(O(\log M)\), and for \(N\) students it’s \(O(N \log M)\)
• Space complexity: \(O(N + M)\)
  • Required for storing arrays \(S\) and \(T\)

Implementation Notes

• bisect_right(T, x) returns the count of elements at most \(x\) in the sorted array \(T\)
• Using bisect_left(T, x) would give the count of elements less than \(x\), so bisect_right is appropriate here
• Since the order of books doesn’t affect the answer, sorting \(T\) is fine (we don’t sort \(S\) because the order of students affects the output)

Source Code

import bisect

def main():
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    T = list(map(int, input().split()))
    
    # Sort T for use with binary search
    T.sort()
    
    # Calculate the number of borrowable books for each student
    for i in range(N):
        # Find the count of T[j] satisfying S[i] >= T[j]
        # In the sorted T, this equals the count of elements at most S[i]
        count = bisect.bisect_right(T, S[i])
        print(count)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.