kmjp's blog

競技プログラミング参加記です

Codeforces #388 Div2 D. Leaving Auction

こちらもDiv2Dとしては若干ややこしい。
http://codeforces.com/contest/749/problem/D

問題

N人で商品のオークションを行う。
時系列で誰が何円を提示したかが与えられる。
これに対して以下のクエリQ個を処理せよ。

各クエリでは、オークションの不参加者の一覧が与えられる。
その際誰が何円で商品を競り落としたか答えよ。
なお、不参加者がいたために自身が複数回連続で提示することになった場合、安いほうの価格で落札する。

解法

まず、だれが競り落とすかを求めよう。
各参加者の最高提示額をPriority_queueなどに入れ、不参加者を取り除けば、残された人のうち最高提示額の提示者がわかる。
なお、自身が連続して提示した場合に安いほうを競り落とすことになるので、最高額で競り落とすとは限らない。
よって、最高提示額の提示者を求めた後、さらにpriority_queueを探索し、2番目の額の提示者を求めよう。

各人の提示額を配列に入れておけば、lower_boundなどで2番目の額の提示者を上回る最安の提示額を求められる。

int N;
int A[202020],B[202020];
int Q;
vector<int> V,fix;
vector<pair<int,int>> P[202020];
int ret[202020];
int del[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i]>>B[i], A[i]--;
		P[A[i]].push_back({B[i],i});
	}
	priority_queue<pair<int,int>> PQ;
	FOR(i,N) if(P[i].size()) PQ.push({P[i].back().first,i});
	
	MINUS(del);
	cin>>Q;
	FOR(i,Q) {
		cin>>x;
		V.resize(x);
		FOR(j,x) {
			cin>>V[j], V[j]--;
			del[V[j]]=i;
		}
		
		pair<int,int> k={-1,-1};
		while(PQ.size()) {
			k=PQ.top();
			PQ.pop();
			fix.push_back(k.second);
			if(del[k.second]!=i) break;
			k={-1,-1};
		}
		if(k.first==-1) {
			cout<<"0 0"<<endl;
			goto out;
		}
		
		while(PQ.size()) {
			if(del[PQ.top().second]!=i) break;
			fix.push_back(PQ.top().second);
			PQ.pop();
		}
		if(PQ.empty()) {
			ret[i]=P[k.second][0].second;
		}
		else {
			auto k2=PQ.top();
			int v=k2.first;
			ret[i]=lower_bound(P[k.second].begin(),P[k.second].end(),k2)->second;
		}
		cout<<A[ret[i]]+1<<" "<<B[ret[i]]<<endl;
		out:
		FORR(f,fix) PQ.push({P[f].back().first,f});
		fix.clear();
	}
	
}

まとめ

ややこしくて結構手こずった。