HHKB プログラミングコンテスト 2020, C : Neq Min

問題文

　https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_c

問題概要

　長さ $N$ の数列 $\{ p_i \}$ がある．各 $i = 1, 2, 3, \dots N$ について，$p_1, p_2, \dots, p_i$ のどれとも一致しない非負整数をそれぞれ求め，$i$ の昇順に出力せよ．

制約

• $1 \leq N, p_i \leq 200{,}000$

解法

　出力するべき非負整数の列は，単調非減少な列になっています．また，最大値は $O( \max p )$ になります．従って，隣接する要素の差の和も $O( \max p )$ です．
　「次に出力するべき値」を変数として保持し，これを適切にメンテナンスすることを考えます．その変数を $k$ と呼ぶことにします．このとき，ある $i$ に対してやるべきことは，

1. $k$ と一致する $p_j$ ($j \leq i$) がある間，$k \leftarrow k + 1$ する
2. $k$ を出力する

です．1. の判定は，各 $p_j$ を std::set に入れておくことで一回あたり $O( \log N )$ 時間で完了できます．また，インクリメントの回数は上述のように $O( \max p )$ 回なので，1. の実行回数も $O( \max p )$ 回です．set への挿入が $O( N )$ 回発生することを合わせると，1. にかかる時間は全体で $O( ( N + \max p ) \log N )$ 時間となります．2. は全体で $O( N )$ 時間で完了するので*1，これで間に合います．

コード

int main()
{
	IN( int, N );
	VI A( N );
	cin >> A;

	int res = 0;
	set< int > s;
	FOR( a, A )
	{
		s.insert( a );
		for ( ; s.find( res ) != end( s ); ++res );
		cout << res << '\n';
	}
	cout << flush;

	return 0;
}

*1:扱う整数のビット長は定数であるものとします