yukicoder : No.649 ここでちょっとQK！

本番無駄に長いコードを書いてしまった。
https://yukicoder.me/problems/no/649

問題

初期状態で空の配列Sがある。
以下のクエリに順次答えよ。

• Sに指定された値vを追加する
• S中で小さい順からK番目の要素が存在すればそれを答え、配列から取り除く。

解法

本番自分は以下の解法で解いた。Kが可変なら良いが、固定だと冗長。

• vを先読みして座標圧縮する。
• BITで各vの登場回数をカウントし、後者のクエリでは二分探索でK番目の要素を求める。

Kが固定ならmultiset2つで解ける。
1つ目はSのうち小さい順K個、2つめは残りを格納する。

• 前者のクエリでは、とりあえず1つ目のmultisetに要素を追加し、K個から溢れるならその分大きい方から順に2つ目に移す。
• 後者のクエリでは、1つめのmultisetの最大値を答えて取り除く。その分2つめから1個補充する。

int Q,K;
multiset<ll> A,B;
ll V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q>>K;
	FOR(i,Q) {
		cin>>x;
		if(x==1) {
			cin>>V;
			A.insert(V);
			if(A.size()>K) {
				B.insert(*A.rbegin());
				A.erase(A.find(*A.rbegin()));
			}
		}
		else {
			if(A.size()==K) {
				cout<<*A.rbegin()<<endl;
				A.erase(A.find(*A.rbegin()));
				if(B.size()) {
					A.insert(*B.begin());
					B.erase(B.begin());
				}
			}
			else {
				cout<<-1<<endl;
			}
		}
	}
	
}

まとめ

トイレに行きたすぎて、とりあえず思いついた方が書いてしまったが冗長でむしろ時間食った感がある。