ABC466 B - Representative Balls

考え方

色ごとに、その色のボールの最大値を探す問題。
指示通りに $1$ 色ずつ調べることもできるが、ここではもっとスマートなやり方を考える。

各色に対し、「今のところの最大値」を保管しておく変数を用意する。
色が $1$ から $M$ までなので、これを 0-indexed に変換し、vector でデータを持てばよい。
そして、それぞれをどんなボールの大きさよりも小さい値で初期化しておく。
ここでは、後述する便利さを考えて、すべて -1 で初期化しておく。

そして、ボールを $1$ つずつ見ていく。
まずは色を確認する。
その後、該当する色の「今のところの最大値」データを更新する。
暫定最大値が a に保管されていて、b がそれより大きければ書き換えたい場合、以下でよい。
今回は a にあたる部分に vector の要素を書くことになる。

a = max(a,b);

これを全ボールについてループで処理する。
すると、$1$ 個でもボールがあった色は、vector 内に、その色のボールの大きさの最大値が入っている。
-1 がどのボールの大きさよりも小さい値であるため、制約上最小のボールでも更新が行われている。
また、その色のボールが $1$ つもなかった場合、初期化した -1 がそのまま入っている。
このような場合は、問題で -1 と答えるよう指示されている。

つまり、この vector を全てそのまま出力すれば、問題に対する答えとなっている。
$2$ 種類の意味の値が混在しているのにまとめて処理できるのが、-1 で初期化した便利さである。

入力例1での動作

入力を受け取る。
色は入力時に $1$ ずつ減らし、0-indexed に直す。

n: 4
m: 5
c: {0, 1, 0, 3}
s: {3, 10, 7, 9}

最初は、各色の最大値を全て $-1$ としておく。

{-1, -1, -1, -1, -1}

ボールを前から順に見たとき、最大値は次のように変化する。

したがって、各色の答えは 7 10 -1 9 -1 となる。

注意点

特になし。

別解

特になし。