QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#515731 | #4880. Network Transfer | chenhongxuan | WA | 702ms | 74868kb | C++14 | 3.1kb | 2024-08-11 22:13:51 | 2024-08-11 22:13:52 |
Judging History
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'