今日はこれの解説をします．
問題概要
\(n\) 人が順に試験を受けます． 人 \(i\) は，\(t_i\) 分かけて試験を受けるか，\(0\) 分かけて試験を放棄することができます．
ここで，試験全体の制限時間は \(M\) 分です． 人 \(i\) が試験に合格するためには，人 \(1\) から人 \(i-1\) までの行動時間の総和と \(t_i\) の和が \(M\) 以下である必要があります．
各 \(i\) について，人 \(i\) が試験に合格するためには人 \(1\) から人 \(i-1\) までのうちの何人が試験を放棄する必要があるかを求めてください． なお，人 \(i\) のために放棄することになった人は，必ずしも人 \(j > i\) のために試験を放棄する必要はありません．
制約
- \(1 \le n \le 2\cdot 10^5\)
- \(1 \le M \le 2\cdot 10^7\)
- \(1 \le t_i \le 100\), \(t_i \le M\) for each \(i\)
考察
とりあえず \(i\) を固定して考えます．
これは当然なんですが，\(t_j\) が大きい人 \(j < i\) から貪欲に選んで放棄させたいです． 逆から見ると，\(t_j\) が小さい人から貪欲に試験を受けさせてあげたいです．
\(t_j\) をソートして \(\sum_{j=0}^k t_j \le M\) となる \(k\) の最大値を求めて，...などをすると答えは出そうなんですが，\(n\) が大きいのでこれはつらそうです．
ところで，\(t_j\) が小さいのでそこに狙いをつけてみましょう． バケット \(b[1\dots 100]\) を用意して，\(k\) 分かかる人を処理し終えたら \(b[k]\) に \(1\) 加えます．
人 \(i\) に対する答えを求めるときは，次のようにします．
まず，\(s \gets t_i\) で初期化します． バケットを先頭から見ていき，注目中のバケットを \(k\) とおきます． \(s + k\cdot b[k] \le M\) であれば，\(s\) に \(k \cdot b[k]\) を足して，続けます（この人たちは試験を受けられることを意味します）． そうでなければ，\(k\) 分かかる人のいくらかは試験を受けられ，残りは受けられないことになります．
// このような \(k\) が存在しなければ答えは 0 です．
この時点で試験の残り時間は \(M-s\) 分なので，\(k\) 分かかる人のうち \(\lfloor (M-s) / k\rfloor\) 人は試験を受けられるとわかります．
よって，\(b[1\dots k -1]\) の総和とこれの和が試験を受けられる人の人数です．求めたいのは放棄させる人数なので，引き算をして終了です．
実装
余談
セグ木を使うと \(t_i\) が大きくても \(O(\log n)\) で処理できます． これはうれしいので，概要をすこし書きます．
人 \(i\) を加える際に，ソートされた順で \(t_i\) を列に加えることができるとうれしいです．
これは平衡二分木（std::set みたいなの）があれば高速にできます．
また，その上で，最初の要素から \(k\) 番目までの要素の和を求められるとうれしいです．
これは std::set ではできませんが，自分で平衡二分木を実装すると高速にできます．
なんですが，このような処理が求められても，クエリ先読みが可能な状況であれば平衡二分木をセグ木で対応できます．
クエリ先読みできるときに平衡二分木をセグ木で代用する一般的なテクみたいな記事をそのうち書きます．
