AtCoder Regular Contest 072F: Dam

http://arc072.contest.atcoder.jp/submissions/1399394

O(N)だからqueueとか使うのかな?と一瞬思ったが、水なんて独立に考えることが出来ないだろ!と思い、O(NlogN)で何とかしようとしたが死亡。

水を入れた順番から昇順にdequeで管理することを考える。

i番目でv[i]Lの水を入れる時、まずfrontからv[i]Lだけ取り出す。
次に、dequeの最後にi番目の水を追加するのだが、dequeの最後の要素がi番目の水より温度が高いなら混ぜてしまう。

int N, L;
deque<pair<double, int>> que;

void solve() {
	cin >> N >> L;

	double res = 0;
	rep(i, 0, N) {
		double a; int b;
		cin >> a >> b;

		int S = L + b;
		while(!que.empty()) {
			pair<double, int> p = que.front();
			if(S - p.sec <= L) {
				que.front().sec -= S - L;
				res -= que.front().fst * (S - L);
				break;
			}
			else {
				S -= que.front().sec;
				res -= que.front().fst * que.front().sec;
				que.pop_front();
			}
		}

		res += a * b;
		cout << res / L << "\n";

		while(!que.empty() && a < que.back().fst) {
			a = (que.back().fst * que.back().sec + a * b) / (b + que.back().sec);
			b += que.back().sec;
			que.pop_back();
		}
		que.push_back(pair<double, int>(a, b));
	}
}

rngさんの解説見たら凸関数で考えていた。確かにそれだったらdeque使うのは自然だね。