Overview

This problem asks us to lend each student “the most interesting book among the books they can read (difficulty ≤ reading ability)” and find the total interestingness. Since the same book can be lent to multiple people, each student can be considered independently.

Analysis

Key Insight

Since the same book can be lent to any number of people, there is no competition for books among students. In other words, for each student, we just need to independently find “the maximum interestingness among books satisfying difficulty \(R_i \leq T_j\)”.

Problem with the Naive Approach

For each student \(j\), if we check all \(M\) books to find the one with \(R_i \leq T_j\) and maximum \(S_i\), the time complexity becomes \(O(N \times M)\). Since \(N, M\) can each be up to \(2 \times 10^5\), this requires up to \(4 \times 10^{10}\) operations in the worst case, which will not fit within the time limit.

Solution Idea

We sort the books in ascending order of difficulty and precompute the prefix maximum of interestingness (prefix max).

For example, when books are arranged in order of difficulty:

Book	Difficulty \(R\)	Interestingness \(S\)	prefix max
A	2	5	5
B	3	8	8
C	5	3	8
D	7	10	10

If a student’s reading ability is \(T_j = 4\), the books with difficulty \(\leq 4\) are A, B, and C. The maximum interestingness among them is immediately found to be \(8\) from the prefix max.

“The position of the last book satisfying difficulty \(\leq T_j\)” can be efficiently found using binary search on the sorted array.

Algorithm

1. Sort the \(M\) books in ascending order of difficulty \(R_i\).
2. Compute the prefix maximum of interestingness (prefix max) in sorted order.
   • prefix_max[k] = the maximum \(S_i\) among the first \(k+1\) books after sorting
3. For each student \(j\):
   • Use binary search (bisect_right) to find the last position pos in the difficulty array that is \(\leq T_j\).
   • If pos >= 0, add prefix_max[pos] to the total (there exists a readable book).
   • If pos < 0, there are no readable books, so add \(0\).
4. Output the total.

Complexity

• Time complexity: \(O(M \log M + N \log M)\)
  • Sorting books takes \(O(M \log M)\)
  • Binary search for each student takes \(O(\log M)\), and for \(N\) students this is \(O(N \log M)\)
• Space complexity: \(O(N + M)\)
  • Storage for book information, prefix max array, and student reading ability array

Implementation Notes

• Usage of bisect_right: bisect_right(difficulties, t) returns “the first position greater than \(t\)”, so subtracting \(1\) from it gives “the last position \(\leq t\)”. Don’t forget to handle the case where the result is \(-1\) (= no readable books).

• Fast input: Since \(N, M\) can be large, we use sys.stdin.buffer.read() to read all input at once for faster I/O.

• Building the prefix max: It can be constructed in a single loop after sorting, allowing each query to be answered in \(O(1)\) (excluding the binary search part).

  Source Code

import sys
from bisect import bisect_right

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    books = []
    for i in range(M):
        s = int(input_data[idx]); idx += 1
        r = int(input_data[idx]); idx += 1
        books.append((r, s))
    
    T = [int(input_data[idx + j]) for j in range(N)]
    idx += N
    
    # Sort books by difficulty
    books.sort()
    
    # Build prefix max of fun values sorted by difficulty
    # For each difficulty threshold, the best fun is the max fun among all books with r <= threshold
    difficulties = []
    prefix_max = []
    current_max = 0
    for r, s in books:
        current_max = max(current_max, s)
        difficulties.append(r)
        prefix_max.append(current_max)
    
    total = 0
    for t in T:
        # Find rightmost book with difficulty <= t
        pos = bisect_right(difficulties, t) - 1
        if pos >= 0:
            total += prefix_max[pos]
    
    print(total)

main()

---

This editorial was generated by claude4.6opus-thinking.