CSAcademy Round #86 : D. Water Tower

Div2回ですがなかなかの出来で良かった。
https://csacademy.com/contest/round-86/task/water-tower/

問題

高さHまで水が満たされた水筒がある。
この水筒は出来が悪く、時刻T[i]に高さH[i]の地点に穴が開く。

水筒に穴が開いていると、時間1当たり、今の水面の高さ以下の穴の数と同じだけ水の高さが減少する。
最終的に水が空になる時刻を求めよ。

解法

水の減少速度が変化する契機は以下のいずれかである。

• 新たに穴が開き、以後水の減少速度が増加する
• 水が減少し、既存の穴のどれかに到達して、以後水の減少速度が減少する

現在の状態から、priotity_queue等用いて上記２種類のイベントのうち時間順に適宜処理していけばよい。

int Q;
double L,T,P;
multiset<int> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L>>Q;
	priority_queue<pair<int,int>> PQ;
	
	FOR(i,Q) {
		cin>>x>>y;
		PQ.push({-x,y});
	}
	
	M.insert(0);
	while(L>0) {
		// next leak;
		double nl=(PQ.size()?-PQ.top().first:1e10);
		// next stop
		double ns=(P>0)?(T+(L-*M.rbegin())/P):1e10;
		
		if(nl==1e10 && ns==1e10) return _P("-1\n");
		if(nl<ns) {
			L-=(nl-T)*P;
			T=nl;
			if(PQ.top().second<L) {
				M.insert(PQ.top().second);
				P++;
			}
			PQ.pop();
		}
		else {
			L=*M.rbegin();
			T=ns;
			M.erase(M.find(*M.rbegin()));
			P--;
		}
	}
	_P("%.12lf\n",T);
}

まとめ

これはすんなりだったかな。