QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#515730 | #4880. Network Transfer | chenhongxuan | WA | 232ms | 41324kb | C++14 | 3.1kb | 2024-08-11 22:12:29 | 2024-08-11 22:12:29 |
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=1e9;
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 5ms
memory: 27444kb
input:
2 10 0 100 2 4 200 1
output:
13.0000000000 30.0000000000
result:
ok 2 numbers
Test #2:
score: 0
Accepted
time: 4ms
memory: 26784kb
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: 27588kb
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: 27548kb
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: 3ms
memory: 28484kb
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: 27840kb
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: 27684kb
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: 27668kb
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: 232ms
memory: 39380kb
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: 212ms
memory: 41324kb
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 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0...
result:
wrong answer 1st numbers differ - expected: '1790041363636.3635254', found: '0.0000000', error = '1.0000000'