QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#515729 | #4880. Network Transfer | chenhongxuan | WA | 262ms | 41460kb | C++14 | 3.1kb | 2024-08-11 22:10:50 | 2024-08-11 22:10:50 |
Judging History
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'