Codeforces #357 Div2 C. Heap Operations

眠いとか体調悪いとかいう日の方がパフォーマンスいいのが謎。
http://codeforces.com/contest/681/problem/C

問題

ヒープに対して以下の操作のいずれかを計N回行った。

• 数値Xをヒープに追加する。
• 最小値を１つヒープから取り除く。
• ヒープの最小値を調べたら値がXだった。

本当はN回以上の操作を行っていたが、うち一部の操作が削られ、入力で与えられるN回が残った。
ヒープ操作に矛盾が起きない範囲で、N個の操作ログを部分列として含むような最小のログを答えよ。

解法

multisetを使い、矛盾が起きないようにヒープへの値の追加・削除を行う。

• 数値Xをヒープに追加する。
  • このケースは愚直にそのままシミュレートする。
• 最小値を１つヒープから取り除く。
  • ヒープ内の要素が空なら適当な値を１個入れるログを挿入する。その後指示通り削除する。
• ヒープの最小値を調べたら値がXだった。
  • ヒープ中X未満の値をすべて取り除く。
  • その後ヒープの先頭がXでないなら、Xを追加するログを挿入する。

string S[3]={"insert","getMin","removeMin"};
int N;
int T[101010],A[101010];
vector<pair<int,int>> V;
multiset<int> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>s;
		FOR(x,3) if(s==S[x]) break;
		
		if(x==0) {
			cin>>x;
			V.push_back({0,x});
			M.insert(x);
		}
		else if(x==1) {
			cin>>x;
			
			while(M.size() && *M.begin()<x) {
				V.push_back({2,0});
				M.erase(M.begin());
			}
			if(M.empty() || *M.begin()>x) {
				V.push_back({0,x});
				M.insert(x);
			}
			
			assert(*M.begin()==x);
			V.push_back({1,x});
		}
		else if(x==2) {
			if(M.empty()) {
				V.push_back({0,0});
				M.insert(0);
			}
			V.push_back({2,0});
			M.erase(M.begin());
		}
	}
	
	_P("%d\n",V.size());
	FORR(r,V) {
		if(r.first<2) _P("%s %d\n",S[r.first].c_str(),r.second);
		else _P("%s\n",S[r.first].c_str());
	}
	
}

まとめ

面倒なだけであまり面白みは感じなかったな…。