ei1903の競プロメモ

競プロの解説など

HOJ 1526 - Contest

HOJ 解説

問題概要

$N \$ 問のコンテストに $\ M \$ 人の部員が参加している。
$i \$ 番目の部員のレーティングは $\ R_i \$ であり、 $l_i \$ 番目から $\ r_i \$ 番目までの問題を解いた。
各問題について、その問題を解いた部員についてのレーティングの平均値を求めよ。

制約

$1 \leq N,M \leq 3 \times 10^5$
$1 \leq R_i \leq 10^9$
$1 \leq l_i \leq r_i \leq N$

解説

各問題について、その問題を解いた部員のレーティングの総和と解いた人の人数が分かればよいです。
愚直に計算すると $\ O(NM) \$ となりTLEですが、各部員の解いた問題が区間となっていることに注目するといもす法が使えることが分かります。
よってこの問題は $\ O(N + M) \$ で解くことができました。