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使うのは自然だね。