Overview

This is a problem where we select the most interesting book among those with difficulty at or below each student’s reading ability, and find the total of those interest values.

Analysis

A naive approach would be to check all books for each student and find the maximum interest value among the books they can read. However, since \(N\) and \(M\) can each be up to \(2 \times 10^5\), an \(O(NM)\) time complexity would not fit within the time limit.

To solve this efficiently, we need the following two observations: 1. Sort the books by difficulty and precompute the maximum interest value available at or below each difficulty level 2. For each student’s reading ability, use binary search to identify the appropriate range of books

Algorithm

1. Preprocessing the books:

   • Sort the books in ascending order of difficulty \(R_i\)
   • Iterate through the sorted books, recording the maximum interest value achievable up to each difficulty level (prefix maximum)

2. Processing the students:

   • For each student’s reading ability \(T_j\), use binary search (bisect_right) to identify the range of books readable with that reading ability or below
   • From the precomputed prefix maximum interest values, retrieve the maximum interest value within that range
   • If there are applicable books, add that interest value to the total sum

Complexity

• Time complexity: \(O((N + M) \log M)\)
  • Sorting the books: \(O(M \log M)\)
  • Computing the prefix maximum: \(O(M)\)
  • Binary search for each student: \(O(N \log M)\)
• Space complexity: \(O(M)\)
  • Arrays for storing book information

Implementation Notes

• Manage books as tuples of (difficulty, interest value) and sort by difficulty

• Use bisect_right to find the position of the maximum difficulty at or below the student’s reading ability

• Prepare a separate array to store the prefix maximum interest values, enabling efficient maximum value retrieval

• Be careful not to add to the total when there are no readable books (i.e., position is 0)

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    n = int(data[0])
    m = int(data[1])
    
    books = []
    index = 2
    for i in range(m):
        s = int(data[index])
        r = int(data[index+1])
        index += 2
        books.append((r, s))
    
    students = list(map(int, data[index:index+n]))
    
    books.sort(key=lambda x: x[0])
    
    max_s = 0
    best_books = []
    for r, s in books:
        if s > max_s:
            max_s = s
        best_books.append((r, max_s))
    
    from bisect import bisect_right
    
    best_books_r = [book[0] for book in best_books]
    best_books_s = [book[1] for book in best_books]
    
    total = 0
    for t in students:
        pos = bisect_right(best_books_r, t)
        if pos > 0:
            total += best_books_s[pos-1]
    
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.