Overview

This is a problem where we need to determine the number of books each user can read, based on the comparison between their reading ability and the difficulty levels of the books.

Analysis

In this problem, for each user \(j\), we need to find “the number of books whose difficulty \(D_i\) is less than or equal to the reading ability \(S_j\).” A naive approach would be to scan all books for each user and check the condition, but this has a time complexity of \(O(N \times M)\), which is impractical given the constraints \(N, M \leq 2 \times 10^5\) (requiring up to \(4 \times 10^{10}\) operations).

Therefore, we need a fast way to find “the number of books with difficulty \(S_j\) or less.” This can be efficiently computed using binary search if we sort the list of book difficulties beforehand. Specifically, by finding “the position of the largest element that is \(S_j\) or less” in the sorted array, we can determine the number of qualifying books.

For example, if the difficulties are \([3, 1, 4]\) and a user’s reading ability is \(4\), sorting gives \([1, 3, 4]\), and binary search tells us that “the number of elements less than or equal to 4” is 3 books.

Algorithm

1. Sort the list of book difficulties \(D\) in ascending order.
2. For each user’s reading ability \(S_j\), use binary search on the sorted \(D\) to find “the number of elements less than or equal to \(S_j\).”
   • In Python, bisect.bisect_right(D, s) returns the first position in the sorted list that exceeds \(s\), so it directly gives “the number of elements less than or equal to \(s\).”
3. Output that value.

Complexity

• Time complexity: \(O(M \log M + N \log M)\)
  • \(M \log M\): Sorting the difficulty list
  • \(N \log M\): Binary search for each user
• Space complexity: \(O(M + N)\)
  • Required to store the lists of difficulties and reading abilities

Implementation Notes

• Don’t forget to sort the book difficulties.
• bisect.bisect_right returns “the first index that exceeds the specified value,” so it directly gives “the number of elements less than or equal to that value.”
• Pay attention to the input and output formats.

## Source Code

```python
import bisect

# 入力の読み込み
N, M = map(int, input().split())
D = list(map(int, input().split()))
S = list(map(int, input().split()))

# 本の難易度をソート
D.sort()

# 各利用者について、読める本の冊数を二分探索で求める
for s in S:
    # 難易度が S[j] 以下の本の冊数は、
    # ソートされた D の中で S[j] 以下の要素の個数に等しい
    count = bisect.bisect_right(D, s)
    print(count)

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