AtCoder ABC #170 : E - Smart Infants

Eは割と簡単目の問題。
https://atcoder.jp/contests/abc170/tasks/abc170_e

問題

N人の幼児がいて、それぞれのレートと属する幼稚園が与えられる。
幼児の属する幼稚園を変更するクエリがQ回行われる。
クエリ毎に、以下の値を答えよ。

• 幼児が1人以上いる幼稚園における、各幼稚園の最大レートの最小値

解法

各幼稚園内のレートを保持するmultisetと、各幼稚園の最大レートを保持するmultisetを持ち、クエリ毎に前者を変更しつつ対応して後者を更新していく。

int N,Q;
int A[202020],B[202020];
multiset<int> K[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		K[B[i]].insert(-A[i]);
	}
	
	multiset<int> cand;
	for(i=1;i<=200000;i++) {
		if(K[i].size()) cand.insert(-*K[i].begin());
	}
	
	while(Q--) {
		int C,D;
		cin>>C>>D;
		C--;
		cand.erase(cand.find(-*K[B[C]].begin()));
		K[B[C]].erase(K[B[C]].find(-A[C]));
		if(K[B[C]].size()) cand.insert(-*K[B[C]].begin());
		B[C]=D;
		if(K[D].size()) cand.erase(cand.find(-*K[D].begin()));
		K[D].insert(-A[C]);
		cand.insert(-*K[D].begin());
		cout<<*cand.begin()<<endl;
	}
	
	
}

まとめ

こういうデータの持ち方はCodeforcesやってるとよく出てくる印象がある。