ABC221 参加記録 - geam1113’s diary

コンテスト中AC:A〜D

$A_i,B_i$ の制約が小さければ、以下のimos法で解けます。

・ $i$ 人目について、配列 $C$ の $C_{A_i}$ に+1、 $C_{A_i + B_i}$ に-1する。

・最後に、 $i$ を2から最大日数まで順に $C_i$ += $C_{i-1}$ する

・ $i$ 日目のログイン数は $C_i$ 人である。

今回制約が大きいので配列保持することはできません。

このときは、イベント情報のみ保持するimos法をおこないます。

配列 $D$ に以下のような情報を追加していきます。

・ $(A_i,\ 1)$

・ $(A_i+B_i,\ -1)$

これは $D_i=(T_i,S_i)$ のとき、時間 $T_i$ に人数が $S_i$ 人増えることを表します。

このイベントを $T_i$ の昇順にソートし、 $S_i$ に対して順に $S_i$ += $S_{i-1}$ します。

こうすると、 $T_{i+1}-T_i$ 日間の間、 $S_i$ 人いることになるので、答えを求めることができます。