Overview

A problem where each student selects the most interesting book from those they can read, and we find the total of those interest values.

Analysis

In this problem, for each student we need to select the book with the highest interest value \(S_i\) among books satisfying the condition “difficulty \(R_i\) ≤ reading ability \(T_j\).” If we use brute force to search for the maximum each time, the complexity becomes \(O(N \times M)\), which is too slow for the given constraints (TLE).

The key observation is that “if we sort the books by difficulty \(R_i\), then the range of books a student with reading ability \(T_j\) can read forms a contiguous prefix.” This allows us to precompute “the maximum interest value among books with difficulty \(R_i\) or less” cumulatively, enabling fast processing of each query. Furthermore, by using binary search on the sorted array to find “the position of the last book with difficulty at most the student’s reading ability,” we can speed up the entire solution.

Algorithm

1. Sort all books in ascending order of difficulty \(R_i\).
2. Create an array max_interest_up_to that cumulatively records the maximum interest value up to each position in the sorted order.
3. For each student’s reading ability \(T_j\), use binary search to find the maximum interest value among books with difficulty at most \(T_j\).
4. Accumulate those interest values into the total.

For example, suppose the books are given as follows: - Book 1: \((S=5, R=3)\) - Book 2: \((S=7, R=1)\) - Book 3: \((S=6, R=4)\)

Sorting by difficulty gives: - Book 2: \((S=7, R=1)\) - Book 1: \((S=5, R=3)\) - Book 3: \((S=6, R=4)\)

The maximum interest value up to each difficulty level is: - Up to difficulty 1: 7 - Up to difficulty 3: max(7, 5) = 7 - Up to difficulty 4: max(7, 5, 6) = 7

Therefore, max_interest_up_to = [7, 7, 7]. If a student’s reading ability is, for example, 3, then the maximum interest value among books with difficulty 3 or less is 7.

Complexity

• Time complexity: \(O(M \log M + N \log M)\)
  • \(O(M \log M)\) for sorting the books, and \(O(N \log M)\) for retrieving the maximum interest value via binary search for each student.
• Space complexity: \(O(M + N)\)
  • For the book list, the cumulative maximum interest table, and the student list.

Implementation Notes

• When using binary search, comparing with a tuple like (difficulty, infinity) allows accurately finding the last element among those with the same difficulty.

• The key point is precomputing “the maximum interest value among books with difficulty \(R_i\) or less.”

• Since multiple students can borrow the same book, no individual tracking is needed.

  Source Code

import sys
from bisect import bisect_right
import heapq

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    books = []
    idx = 2
    for _ in range(M):
        s = int(data[idx])
        r = int(data[idx+1])
        books.append((r, s))
        idx += 2
    
    # 難易度でソート
    books.sort()
    
    # 難易度ごとの最大面白さを計算
    max_interest_up_to = [0] * M
    max_s = 0
    for i in range(M):
        max_s = max(max_s, books[i][1])
        max_interest_up_to[i] = max_s
    
    # 生徒の読解力を読み込み
    students = list(map(int, data[idx:idx+N]))
    
    total = 0
    for t in students:
        # 読める本のうち、難易度 <= t である最大のindexを二分探索
        pos = bisect_right(books, (t, float('inf'))) - 1
        if pos >= 0:
            total += max_interest_up_to[pos]
    
    print(total)

if __name__ == "__main__":
    main()

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