QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#515733 | #4880. Network Transfer | chenhongxuan | TL | 781ms | 74856kb | C++20 | 5.0kb | 2024-08-11 22:16:47 | 2024-08-11 22:16:47 |
Judging History
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 ...