[AtCoder] ABC 170 E – Smart Infants

問題

方針

ある集合の最大値を管理し、その集合の最大値の中の最小値を答える問題です。これは、multiset を使って管理できるそうです。multiset は順序が保たれます。

ここで、幼稚園 \( i \) のレートの集合を \( S_i \) とし、各幼稚園の最大値の集合を \( T \) とします。まず初めに、\( N \) 人の幼稚園児の情報を \( S_i, T \) に反映させます。

幼稚園児 \( i \) が 幼稚園 \( c \) から \( d \) に転園するとして以下の処理を考えます。

転園処理

\( \max(S_c) = A_i\) のとき

\( T \) から \( A_i \) を削除します。さらに、\( S_c \) の中で \( A_i \) の個数が \( 1 \) かつ \( |S_c| \geq 2\) のとき、\( T \) に \( S_c \) の中で \( 2 \) 番目に大きい値を追加します。また、\(S_c \) から \( A_i \) を削除します。

\( \max(S_c) < A_i\) のとき

\( T \) から \( A_i \) を削除します。\( T \) に \( S_c \) の中で \( 2 \) 番目に大きい値を追加します。また、\(S_c \) から \( A_i \) を削除します。

上記以外のとき

\(S_c \) から \( A_i \) を削除します。

入園処理

\( |S_d| = 0 \) または \( \max(S_d) = A_i \)のとき

\( T \) に \( A_i \) を追加します。\( S_d \) に \(A_i \) を追加します。

\( \max(S_d) < A_i \) のとき

\( T \) から \( \max(S_d) \) を削除し、\( T \) に \( A_i \) を追加します。\( S_d \) に \(A_i \) を追加します。

また、入園処理と退園処理が終わったとき、幼稚園児の所属を更新します。

コード