QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515733#4880. Network TransferchenhongxuanTL 781ms74856kbC++205.0kb2024-08-11 22:16:472024-08-11 22:16:47

Judging History

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

  • [2024-08-11 22:16:47]
  • 评测
  • 测评结果:TL
  • 用时:781ms
  • 内存:74856kb
  • [2024-08-11 22:16:47]
  • 提交

answer

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#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=1e15;
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: 41488kb

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

input:

2 10
30 200 1
10 100 2

output:

50.0000000000
20.0000000000

result:

ok 2 numbers

Test #3:

score: 0
Accepted
time: 4ms
memory: 41916kb

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: 4ms
memory: 41556kb

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: 4ms
memory: 42372kb

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

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

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

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: 683ms
memory: 74816kb

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: 0
Accepted
time: 772ms
memory: 72704kb

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:

1790041363636.3626340628
1390577580645.1608160734
1300784647887.3235919476
1280812465753.4243324995
1190840487804.8778631687
1859583333333.3322765827
1410498166666.6661562920
1750241923076.9221084118
1660420857142.8562675714
1180833975903.6142830849
1430416379310.3442841768
1170834642857.1426947117
...

result:

ok 200000 numbers

Test #11:

score: 0
Accepted
time: 767ms
memory: 74840kb

input:

199293 5
9504657 9159218 4
9229606 9939393 93
9949326 9400061 74
9049202 9678955 63
9856746 9805686 100
9900514 9492706 58
9077984 9828311 42
9082259 9783365 78
9815702 9654015 95
9655893 9753916 11
9027905 9930425 9
9210664 9496857 85
9488366 9132506 56
9416678 9238290 2
9475297 9343399 28
9442121 ...

output:

372606864555.1232993901
212211534775.6533226371
238948149663.0400282145
263425611185.3534324169
197063144013.4950600863
270580494646.0317242146
303467045798.2551174164
237141228118.9243829399
203504180187.0508348346
360171498662.9447310567
364170179095.5721946359
219530866865.6281335503
270186214835...

result:

ok 199293 numbers

Test #12:

score: 0
Accepted
time: 778ms
memory: 72756kb

input:

199775 5
9573917 9665464 57
9498813 9469832 81
9885957 9606395 14
9397765 9003071 9
9246019 9070405 26
9740136 9081183 11
9893308 9667485 60
9912483 9414387 94
9934996 9683245 7
9359993 9793294 90
9852046 9209808 22
9704268 9048813 52
9066664 9842295 49
9894656 9914370 56
9520915 9685732 36
9507809 ...

output:

275136188681.6225461066
227063705577.1873306036
355194309827.0368518829
363385338618.7691849768
329856159627.1660505831
359600267866.4127953351
269538859112.9436513036
201263971424.1474483907
368365549271.4343172908
215596647879.4337639362
338462086635.5121387541
277864582191.7766219378
291752383805...

result:

ok 199775 numbers

Test #13:

score: 0
Accepted
time: 781ms
memory: 74852kb

input:

199876 10
9569180 9097026 11
9805018 9888590 69
9859588 9812730 54
9708644 9290190 38
9672977 9335125 45
9617443 9706660 56
9670948 9431976 69
9705708 9008410 2
9091288 9600793 23
9064094 9794988 56
9750869 9563190 30
9234184 9600771 22
9681961 9478086 50
9410316 9590449 15
9604218 9991066 51
957349...

output:

179887507879.3514213860
127724903099.1158379242
141024141836.3508920521
153787858998.0349829048
147195733048.1178967357
138618997279.5911295712
124676275642.3483761027
188810825750.2611270249
169163511122.1318707466
139088289036.2437914014
162417585447.2032651901
170108072542.1166240722
143081618014...

result:

ok 199876 numbers

Test #14:

score: 0
Accepted
time: 777ms
memory: 74808kb

input:

199977 4
9602127 9565587 73
9111223 9419029 57
9833218 9019063 97
9020206 9577308 79
9062250 9637529 67
9457065 9295138 1
9448587 9234150 78
9535931 9639433 15
9247581 9592339 40
9768195 9797367 34
9649692 9879574 35
9727787 9190412 97
9260259 9150191 43
9851295 9229529 69
9724520 9333397 67
9676184...

output:

304491753262.7385893166
340031067721.0189880133
234313922207.0672337562
290561445183.4440272450
319806025765.5412364006
474840344781.4696150720
286089986044.7302128077
441518236521.8439817429
382411279202.5605627596
398221219099.1605739295
396587568673.4485207796
238678764660.4854459465
370475863738...

result:

ok 199977 numbers

Test #15:

score: 0
Accepted
time: 776ms
memory: 74856kb

input:

199077 6
9634388 9960151 22
9418114 9874787 41
9769850 9225397 37
9368769 9901425 8
9489208 9902249 82
9371370 9920615 49
9263226 9036325 88
9329155 9233456 23
9366876 9584570 56
9434611 9799061 9
9473832 9195956 44
9220704 9779369 72
9801558 9822981 43
9366955 9830926 27
9770139 9638731 78
9741872 ...

output:

283688147387.3328517079
254552170732.0875796229
256675980123.5537600666
304680729443.0343797207
192633843521.3563963920
242706661004.9935357571
170818527368.7013964057
279445737169.9180591404
229155389462.9848937094
303032608931.1428124905
245028698316.4499681890
206387719766.6676303148
251159922565...

result:

ok 199077 numbers

Test #16:

score: -100
Time Limit Exceeded

input:

199174 94
4939842 606 76
1166421 867 100
9051103 784 55
8172658 675 51
3743680 551 61
2613139 796 25
6619357 995 81
4244151 919 13
1565998 618 89
8971567 956 48
4453079 696 6
6507538 985 84
821657 762 98
5429287 786 27
6562208 661 86
286640 615 36
6512669 689 74
219589 615 49
8412173 719 58
8817089 ...

output:


result: