Submission #4028570

---

Source Code Expand

#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>
#include <random>

using namespace std;
typedef long long LL;
typedef pair<double,LL> P;

const int S=5e5+10;
double ts[S];
LL vs[S];
int N;
double L;
int main() {
	cout.precision(17);
	cin >> N >> L;
	double sum=0;
	LL sumv=0;
	int s=0; 
	vector<P> q;
	for(int i=0;i<N;i++){
		cin >> ts[i];
		cin >> vs[i];
		if(s<q.size()&&q.back().first>ts[i]){
			if(q.back().second+vs[i]>=L){
				auto t=(vs[i]*ts[i]+(L-vs[i])*q.back().first)/L;
				auto v=L;
				sum+=t*v;
				sumv+=v;
				q.push_back(P(t,v));
			}
			else{
				sum+=ts[i]*vs[i];
				sumv+=vs[i];
				auto v=vs[i]+q.back().second;
				auto t=(vs[i]*ts[i]+q.back().second*q.back().first)/v;
				q.back()=P(t,v);
			}
		}
		else{
			sum+=ts[i]*vs[i];
			sumv+=vs[i];
			q.push_back(P(ts[i],vs[i]));
		}
		while(sumv>L){
			if(sumv-q[s].second>=L){
				sumv-=q[s].second;
				sum-=q[s].first*q[s].second;
				s++;
			}
			else{
				LL d=sumv-L;
				sumv-=d;
				sum-=q[s].first*d;
				q[s].second-=d;
			}
		}
		cout << sum/L << endl;
	}

	return 0;
}

Submission Info

Judge Result