QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#21278 | #2822. 不等式 | DaBenZhongXiaSongKuaiDi# | WA | 0ms | 18184kb | C++20 | 1.6kb | 2022-03-04 14:25:16 | 2022-05-08 02:49:23 |
Judging History
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'