概要

各生徒の読解力 \(T_j\) 以下で読める本の中から「面白さ」の最大値を選び、その合計を求める問題です（本は何度でも貸せるので、生徒ごとに独立に最適化できます）。

考察

• 同じ本を複数人に貸し出せるため、「本の取り合い」は起きません。よって各生徒 \(j\) について
  条件 \(R_i \le T_j\) を満たす本の面白さ \(S_i\) の最大値 を求めればよいです。読める本がなければ \(0\) です。
• 素朴にやると、生徒ごとに全ての本を見て最大を取るので \(O(NM)\) になり、最大で \((2\times 10^5)^2\) と大きすぎて TLE します。
• 重要な観察は、「難易度 \(R\) の上限が増えるほど、選べる本の集合は増え、最大面白さは単調に増える（減らない）」という点です。
  そこで、本を難易度でソートし、難易度が小さい順に見たときの面白さの最大値（前計算） を作ると、各生徒の答えを二分探索で高速に求められます。

例：本を難易度順に並べると - 難易度: \([2, 4, 7, 7]\) - 面白さ: \([3, 5, 1, 10]\) このとき「ここまでに出た最大面白さ」は - prefix max: \([3, 5, 5, 10]\) 読解力 \(T=6\) の生徒は難易度 \(\le 6\) まで（\(2,4\)）読めるので答えは \(5\)、\(T=7\) なら答えは \(10\) になります。

アルゴリズム

1. 本の情報を \((R_i, S_i)\) として配列に入れ、難易度 \(R_i\) の昇順にソートする。
2. ソート後の配列に対して
   • 難易度だけの配列 Rs
   • 「先頭から \(i\) 番目まででの面白さ最大値」配列 pref（prefix maximum） を作る。
     pref[i] = max(pref[i-1], S_i) と更新していけばよい。
3. 各生徒の読解力 \(T_j\) について、
   • Rs の中で \(R \le T_j\) を満たす最後の位置 idx を二分探索で求める（bisect_right(Rs, T_j) - 1）。
   • idx >= 0 なら答えに pref[idx] を加える。そうでなければ読める本がないので加えない（\(0\)）。

これで「条件を満たす中での最大面白さ」を、前計算＋二分探索で高速に求められます。

計算量

• 時間計算量: ソート \(O(M \log M)\) ＋ 各生徒の二分探索 \(O(N \log M)\) なので全体で \(O((N+M)\log M)\)
• 空間計算量: 本と前計算配列で \(O(M)\)（入力配列を除いても同程度）

実装のポイント

• bisect_right(Rs, t) - 1 は「\(R \le t\) を満たす最後の添字」を返します。読める本が1冊もない場合は -1 になるので、idx >= 0 のチェックが必要です。

• 同じ難易度の本が複数あっても、pref が「そこまでの最大」を持っているため正しく処理できます。

• 入力が大きいので、Python では sys.stdin.buffer.read() でまとめて読み取ると高速です。

  ソースコード

import sys
import bisect

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)

    books = []
    for _ in range(M):
        S = next(it)
        R = next(it)
        books.append((R, S))
    Ts = [next(it) for _ in range(N)]

    books.sort()
    Rs = [0] * M
    pref = [0] * M
    cur = 0
    for i, (r, s) in enumerate(books):
        Rs[i] = r
        if s > cur:
            cur = s
        pref[i] = cur

    ans = 0
    for t in Ts:
        idx = bisect.bisect_right(Rs, t) - 1
        if idx >= 0:
            ans += pref[idx]
    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。