(C++使用者向けの内容です。)

次の要件を満たすデータ構造があればこの問題を解くことができます。

• (多重)集合 $S$ に $X$ を追加する。
• $S$ の $K$ 番目の値を求める。

これらのクエリは、g++拡張によって使える tree というデータ構造を使うことで効率的に処理することができます。

このデータ構造はC++のsetの上位互換のような感覚で、(多重でない)集合において $k$ 番目の値を返すことや $k$ 未満の数が何個あるかを知ることができます。
参考記事
参考記事

実装例
(cincout高速化をしていないので1227msですが、高速化をすることで800ms以上速くなります。)