QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#515730#4880. Network TransferchenhongxuanWA 232ms41324kbC++143.1kb2024-08-11 22:12:292024-08-11 22:12:29

Judging History

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

  • [2024-08-11 22:12:29]
  • 评测
  • 测评结果:WA
  • 用时:232ms
  • 内存:41324kb
  • [2024-08-11 22:12:29]
  • 提交

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'