#include #include #include #include #include using namespace std; struct fi { int T; int S; double R; double E; }; int main() { int N, V; ifstream fin("transfer.in"); fin >> N >> V; vector fs; vector is; vector ts; fs.resize(N); for (int i = 0; i < N; i++) { fi& f = fs[i]; fin >> f.T >> f.S; ts.push_back(f.T); f.R = f.S; f.E = 0; is.push_back(i); } sort(ts.begin(), ts.end(), greater()); sort(is.begin(), is.end(), [fs](int l, int r) -> bool {return fs[l].T < fs[r].T; }); vector::iterator l = unique(ts.begin(), ts.end()); ts.erase(l, ts.end()); double lt = 0; int k = 0, s = 0; int si = 0, ei = N; while (!ts.empty() && s < N) { double ct = ts.back(); ts.pop_back(); if (lt > 0 && k > 0) { double dr = (ct - lt) * V / k; for (int i = si; i < ei; i++) { fi& f = fs[is[i]]; if (f.T <= lt && f.R > 0) { if (f.R <= dr) { f.E = ct; f.R = 0; s++; } else f.R -= dr; } } } lt = ct; k = 0; bool ssi = true; ei = N; for (int i = si; i < N; i++) { fi& f = fs[is[i]]; if (f.T <= ct && f.R > 0) { k++; if (ssi) si = i; ssi = false; } if (f.T > ct) { ei = i; break; } } if (ssi) si = 0; if (k > 0) { double nt = ts.empty() ? numeric_limits::max() : ts.back(), mr = numeric_limits::max(); for (int i = si; i < ei; i++) { fi& f = fs[is[i]]; if (f.T <= ct && f.R > 0) { if (mr > f.R) mr = f.R; } } double v = V / k; double dt = mr / V * k; if (ct + dt < nt) ts.push_back(ct + dt); } } ofstream fout("transfer.out"); for (int i = 0; i < N; i++) fout << fs[i].E << endl; }