QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515729#4880. Network TransferchenhongxuanWA 262ms41460kbC++143.1kb2024-08-11 22:10:502024-08-11 22:10:50

Judging History

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

  • [2024-08-11 22:10:50]
  • 评测
  • 测评结果:WA
  • 用时:262ms
  • 内存:41460kb
  • [2024-08-11 22:10:50]
  • 提交

answer

#pragma GCC optimize(2)

#include <bits/stdc++.h>
#define int long long
#define ll 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("%.10f\n",ans[i]);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 27036kb

input:

2 10
0 100 2
4 200 1

output:

13.0000000000
30.0000000000

result:

ok 2 numbers

Test #2:

score: 0
Accepted
time: 3ms
memory: 28684kb

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: 27716kb

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: 3ms
memory: 27404kb

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: 0ms
memory: 27184kb

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: 3ms
memory: 27988kb

input:

1 10000000
10000000 1 1

output:

10000000.0000001006

result:

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

Test #7:

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

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: 3ms
memory: 27560kb

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: 217ms
memory: 41460kb

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:

2000009999998.7763671875
2000009999998.7768554688
2000009999998.7768554688
2000009999998.7768554688
2000009999998.7768554688
2000009999998.7773437500
2000009999998.7770996094
2000009999998.7763671875
2000009999998.7761230469
2000009999998.7761230469
2000009999998.7763671875
2000009999998.7763671875
...

result:

ok 200000 numbers

Test #10:

score: -100
Wrong Answer
time: 262ms
memory: 38524kb

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:

101153076088932.5000000000
101166133474518.3906250000
101195792510768.1250000000
101201212872145.3906250000
101220754436077.1562500000
101075205957010.5625000000
101157579647097.5156250000
101178750179249.8125000000
101215102959469.5937500000
101222711233653.8906250000
101147978518206.7812500000
101...

result:

wrong answer 1st numbers differ - expected: '1790041363636.3635254', found: '101153076088932.5000000', error = '55.5087926'