ARC 042 A - 掲示板 - sky’s 雑記

ギョームでも取り扱いそうな問題.

diff 855

回答時の方針

まずは全探索.

愚直にやると書き込みがあったスレッドのインデックスを0にしてそれ以外のインデックスを+1する,これをm回繰り返せば期待する結果にはなるが計算量は $O(NM)$ で最大 $10^{10}$ で間に合わない.

構造的にpriority_queueとか使えそうだなと思ってスレッド番号と書き込まれた順をpairにしてpushしようとしたが同じスレッドに複数回書き込んだ場合に対応できないと思い断念.書き込んだ順にソートする実装がうまくできずに別の方法を取ることにした.

同じスレッドに複数回書き込みがあったとしても常に最新のもののみ採用すれば良いと気付き同じスレッドでも別物としてvector<ll>にpushして探索済みフラグで対応することにしてAC.

ほぼほぼ上記の通りだがデータ構造的にはvector<pair<ll, ll>>をソートすればよかった.keyにスレッド番号valueに書き込まれた順番を持ってきてソートすればok.

REP(i, n) {
  v[i] = PAIR(10000000 + i, i);
}
REP(i, m) {
  v[a[i] - 1].first = m-i;
}