QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515731#4880. Network TransferchenhongxuanWA 702ms74868kbC++143.1kb2024-08-11 22:13:512024-08-11 22:13:52

Judging History

你现在查看的是最新测评结果

  • [2024-08-11 22:13:52]
  • 评测
  • 测评结果:WA
  • 用时:702ms
  • 内存:74868kb
  • [2024-08-11 22:13:51]
  • 提交

answer

#pragma GCC optimize(2)

#include <bits/stdc++.h>
#define int long long
#define ll long double
#define pb push_back
#define lc p<<1
#define rc p<<1|1
#define st first
#define nd second
//#define pii pair<int,int>
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f^=ch=='-';
	for(;isdigit(ch);ch=getchar())x=x*10+(ch^48);
	return f?x:-x;
}
const int N=2e5+5;
const ll inf=1e12;
int n;
ll w,ans[N],T[N],S[N],P[N];
pair<ll,pair<ll,pair<ll,int>>> a[N];
struct SegmentTree{
	pair<ll,int> val[N<<2];
	ll add[N<<2],mul[N<<2];
	void pushdown(int p){
		//mul
		val[lc].st*=mul[p];	val[rc].st*=mul[p];
		add[lc]*=mul[p];	add[rc]*=mul[p];
		mul[lc]*=mul[p];	mul[rc]*=mul[p];
		mul[p]=1.000;
		//add
		val[lc].st+=add[p];	val[rc].st+=add[p];
		add[lc]+=add[p];	add[rc]+=add[p];
		add[p]=0.000;
		return;
	}
	//集体乘以x 
	void modify1(int p,int l,int r,int L,int R,ll x){
		if(L<=l&&r<=R){
			val[p].st*=x;
			add[p]*=x;
			mul[p]*=x;
			return;
		}
		pushdown(p);
		int mid=(l+r)>>1;
		if(L<=mid)modify1(lc,l,mid,L,R,x);
		if(mid<R)modify1(rc,mid+1,r,L,R,x);
		val[p]=min(val[lc],val[rc]);
	}
	//集体增加x 
	void modify2(int p,int l,int r,int L,int R,ll x){
		if(L<=l&&r<=R){
			val[p].st+=x;
			add[p]+=x;
			return;
		}
		pushdown(p);
		int mid=(l+r)>>1;
		if(L<=mid)modify2(lc,l,mid,L,R,x);
		if(mid<R)modify2(rc,mid+1,r,L,R,x);
		val[p]=min(val[lc],val[rc]);
	}
	pair<ll,int> query(int p,int l,int r,int L,int R){
		if(L<=l&&r<=R)return val[p];
		pushdown(p);
		int mid=(l+r)>>1;
		if(R<=mid)return query(lc,l,mid,L,R);
		if(mid<L)return query(rc,mid+1,r,L,R);
		return min(query(lc,l,mid,L,R),query(rc,mid+1,r,L,R));
	}
	void construct(int p,int l,int r){
		add[p]=0.0000;
		mul[p]=1.0000;
		val[p]={inf,l};
		if(l==r)return;
		int mid=(l+r)>>1;
		construct(lc,l,mid);
		construct(rc,mid+1,r);
	}
}f;
signed main(){
	n=read(),w=read();
	for(int i=1;i<=n;++i){
		ll t=read(),s=read(),p=read();
		T[i]=t;
		S[i]=s;
		P[i]=p;
		a[i]={t,{s,{p,i}}};
	}
	sort(a+1,a+n+1);
	f.construct(1,1,n);
	ll now=0.000,sump=0.000;
	int cnt=0;
	for(int i=1;i<=n;++i){
		ll t=a[i].st,s=a[i].nd.st,p=a[i].nd.nd.st;
		int pos=a[i].nd.nd.nd,idx;
		ll rate;
		pair<ll,int> x=f.query(1,1,n,1,n);
		while(cnt&&x.st<=t-now){
			--cnt;
			ll d=x.st;
			now+=x.st;
			idx=x.nd;
			ans[idx]=now;
			rate=(sump-P[idx])/sump;
			sump-=P[idx];
			f.modify2(1,1,n,1,n,-d);
			f.modify1(1,1,n,1,n,rate);
			f.modify2(1,1,n,idx,idx,inf);
			x=f.query(1,1,n,1,n);
		}
		f.modify2(1,1,n,1,n,-(t-now));
		now=t;
		x=f.query(1,1,n,pos,pos);
		f.modify2(1,1,n,pos,pos,-x.st);
		if(cnt){
			rate=(sump+p)/sump;
			f.modify1(1,1,n,1,n,rate);
		}
		sump+=p;
		ll tmd=(s/(w*(p/sump)));
		f.modify2(1,1,n,pos,pos,tmd);
		++cnt;
	}
	while(cnt){
		pair<ll,int> x=f.query(1,1,n,1,n);
		--cnt;
		ll d=x.st;
		now+=x.st;
		int idx=x.nd;
		ans[idx]=now;
		ll rate=(sump-P[idx])/sump;
		sump-=P[idx];
		f.modify2(1,1,n,1,n,-d);
		f.modify1(1,1,n,1,n,rate);
		f.modify2(1,1,n,idx,idx,inf);
	}
	for(int i=1;i<=n;++i){
		printf("%.10Lf\n",ans[i]);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 42344kb

input:

2 10
0 100 2
4 200 1

output:

13.0000000000
30.0000000000

result:

ok 2 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 38948kb

input:

2 10
30 200 1
10 100 2

output:

50.0000000000
20.0000000000

result:

ok 2 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 43140kb

input:

1 10000000
0 1 42

output:

0.0000001000

result:

ok found '0.0000001', expected '0.0000001', error '0.0000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 41168kb

input:

1 10000000
42 1 42

output:

42.0000001000

result:

ok found '42.0000001', expected '42.0000001', error '0.0000000'

Test #5:

score: 0
Accepted
time: 6ms
memory: 42676kb

input:

1 10000000
42 10000000 42

output:

43.0000000000

result:

ok found '43.0000000', expected '43.0000000', error '0.0000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 43088kb

input:

1 10000000
10000000 1 1

output:

10000000.0000001000

result:

ok found '10000000.0000001', expected '10000000.0000001', error '0.0000000'

Test #7:

score: 0
Accepted
time: 7ms
memory: 42124kb

input:

1 10000000
1 1 100

output:

1.0000001000

result:

ok found '1.0000001', expected '1.0000001', error '0.0000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 42420kb

input:

1 1
10000000 10000000 100

output:

20000000.0000000000

result:

ok found '20000000.0000000', expected '20000000.0000000', error '0.0000000'

Test #9:

score: 0
Accepted
time: 702ms
memory: 72148kb

input:

200000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10000000 1
10000000 10...

output:

2000009999999.9993913174
2000009999999.9993913174
2000009999999.9993913174
2000009999999.9993913174
2000009999999.9993914366
2000009999999.9993913174
2000009999999.9993914366
2000009999999.9993913174
2000009999999.9993913174
2000009999999.9993913174
2000009999999.9993913174
2000009999999.9993913174
...

result:

ok 200000 numbers

Test #10:

score: -100
Wrong Answer
time: 700ms
memory: 74868kb

input:

200000 1
10000000 10000000 22
10000000 10000000 62
10000000 10000000 71
10000000 10000000 73
10000000 10000000 82
10000000 10000000 15
10000000 10000000 60
10000000 10000000 26
10000000 10000000 35
10000000 10000000 83
10000000 10000000 58
10000000 10000000 84
10000000 10000000 23
10000000 10000000 ...

output:

0.0000000000
1390577580645.1608160734
1300784647887.3235919476
1280812465753.4243324995
1190840487804.8778631687
0.0000000000
1410498166666.6661562920
0.0000000000
0.0000000000
1180833975903.6142830849
1430416379310.3442841768
1170834642857.1426947117
0.0000000000
0.0000000000
1250849473684.21024763...

result:

wrong answer 1st numbers differ - expected: '1790041363636.3635254', found: '0.0000000', error = '1.0000000'