QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#21278#2822. 不等式DaBenZhongXiaSongKuaiDi#WA 0ms18184kbC++201.6kb2022-03-04 14:25:162022-05-08 02:49:23

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-08 02:49:23]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:18184kb
  • [2022-03-04 14:25:16]
  • 提交

answer

#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=5e5+10;
db a[N],b[N],Zero[N],v[N],S;
int n,z[N],len;
db tmp[N];
db sum[N<<2],s[N<<2];
#define lson (id<<1)
#define rson (id<<1|1)
#define mid ((l+r)>>1)
const db eps=1e-8;
void update(int id){
	sum[id]=sum[lson]+sum[rson];
	s[id]=s[lson]+s[rson];
}
void add(int id,int l,int r,int pos,db k1,db k2){
	if(l==r){
		sum[id]+=k1;
		s[id]+=k2;
		return;
	}
	if(pos<=mid) add(lson,l,mid,pos,k1,k2);
	else add(rson,mid+1,r,pos,k1,k2);
	update(id);
}
int Find(int id,int l,int r,db k){
	if(l==r)return l;
	if(sum[lson]>k||fabs(sum[lson]-k)<eps) return Find(lson,l,mid,k);
	else return Find(rson,mid+1,r,k-sum[lson]);
}
db query1(int id,int l,int r,int L,int R){
	if(r<L||R<l)return 0;
	if(L<=l&&r<=R)return sum[id];
	return query1(lson,l,mid,L,R)+query1(rson,mid+1,r,L,R);
}
db query2(int id,int l,int r,int L,int R){
	if(r<L||R<l)return 0;
	if(L<=l&&r<=R)return s[id];
	return query2(lson,l,mid,L,R)+query2(rson,mid+1,r,L,R);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
	for(int i=1;i<=n;i++) scanf("%lf",&b[i]);
	for(int i=1;i<=n;i++){
		v[i]=Zero[i]=-b[i]/a[i];
	}
	sort(v+1,v+1+n);
	for(int i=1;i<=n;i++){
		if(fabs(tmp[len]-v[i])>eps){
			tmp[++len]=v[i];
		}
	}
	memset(v,0.0,sizeof(v));
	for(int i=1;i<=len;i++) v[i]=tmp[i];
	for(int i=1;i<=n;i++) z[i]=lower_bound(v+1,v+1+len,Zero[i])-v;
	for(int i=1;i<=n;i++){
		add(1,1,len,z[i],a[i],b[i]);
		S+=a[i];
		int k=Find(1,1,len,S/2);
		printf("%.6lf\n",v[k]*(query1(1,1,len,1,k-1)-query1(1,1,len,k+1,len))-query2(1,1,len,k+1,len)+query2(1,1,len,1,k-1));
	}
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 18184kb

input:

1000
61238 60248 73732 -26564 -93007 4478 -39783 -29386 6714 -96099 58853 29344 88517 -7643 -16343 97123 82004 96690 -63916 13672 -72104 -93128 -33526 4108 -5475 -53323 57787 15891 -9523 -10161 -96799 -83119 77140 97223 -56595 -95821 24758 73652 58307 -22694 -62422 2448 59087 -47128 67302 -53844 -61...

output:

0.000000
21040.367484
46739.801169
-25072.784839
-45512.979392
-40766.381822
-101713.123490
-199042.627407
-125025.845970
-203029.370064
-87626.197135
-47617.382279
-44239.485116
-48469.690613
-54088.272264
-33135.352011
-17556.230779
33600.975338
-26863.434244
-16755.968255
-36466.867468
-125087.27...

result:

wrong answer 4th numbers differ - expected: '118552.3871780', found: '-25072.7848390', error = '1.2114912'