Submission #5563032

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;
typedef double db;
int N,L;

int T[500005],V[500005];
db SM[500005],vv[500005],tt[500005];
db smv[500005];
int ql,qr;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
inline int R()
{
	char t=GC;
	int x=0;
	while(!isdigit(t)) t=GC;
	while(isdigit(t)) x=x*10+t-48,t=GC;
	return x;
}
int main() {
	N = R(); L = R();
	for(int i=1;i<=N;i++) {
		T[i] = R(); V[i] = R();
	}
	printf("%d\n",T[1]);
	ql = qr = 1;
	vv[1] = V[1];
	tt[1] = T[1];
	smv[1] = V[1];
	SM[1] = vv[1] * tt[1];
	for(int i=2;i<=N;i++) {
		if(T[i]<=tt[qr]) {
			db maxv = min(1.0*L-1.0*V[i],1.0*vv[qr]);
			db nt = (tt[qr]*maxv + 1.0*V[i]*T[i]) / (maxv+V[i]);
			vv[qr] = V[i] + maxv;
			
			smv[qr] = smv[qr-1] + vv[qr];
			tt[qr] = nt;
			SM[qr] = SM[qr-1] + tt[qr] * vv[qr];
		} else {
			++qr;
			vv[qr] = V[i];
			tt[qr]  = T[i];
			
			smv[qr] = smv[qr-1] + vv[qr];
			SM[qr] = SM[qr-1] + tt[qr] * vv[qr];
		}
		while(ql<qr&&smv[qr]-smv[ql]>L) ql++;
		db ans = SM[qr] - SM[ql] + 1.0*(L-smv[qr]+smv[ql])*tt[ql];
		printf("%.8f\n",1.0*ans/L);
	}
}

Submission Info

Judge Result