QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#21406 | #2822. 不等式 | qingyu_orz# | WA | 0ms | 11988kb | C++20 | 1.5kb | 2022-03-04 20:05:59 | 2022-05-08 03:12:29 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct apple{
int a,b;
bool operator<(const apple &other)const{
return 1ll*a*other.b>1ll*b*other.a;
}
}e[500005];
int ss[500005];
long long sm[2000005];
double s2[2000005];
int A[500005],B[500005];
void add(int l,int r,int o,int x,int v){
if(v==0)return;
if(l==r){
sm[o]+=v,s2[o]+=1.0*v*e[x].b/e[x].a;
return;
}
int mid=(l+r)>>1;
if(x<=mid)add(l,mid,o<<1,x,v);
else add(mid+1,r,o<<1|1,x,v);
sm[o]=sm[o<<1]+sm[o<<1|1];
s2[o]=s2[o<<1]+s2[o<<1|1];
}
int query(int l,int r,int o,long long pm){
if(l==r)return l;
int mid=(l+r)>>1;
if(pm<=sm[o<<1])return query(l,mid,o<<1,pm);
return query(mid+1,r,o<<1|1,pm-sm[o<<1]);
}
double query2(int l,int r,int o,int x,double zz){
if(l==r){
return 0;
}
int mid=(l+r)>>1;
if(x<=mid){
double ans=s2[o<<1|1]-sm[o<<1|1]*zz;
return ans+query2(l,mid,o<<1,x,zz);
}
double ans=sm[o<<1]*zz-s2[o<<1];
return ans+query2(mid+1,r,o<<1|1,x,zz);
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;++i){
scanf("%d%d",&e[i].a,&e[i].b);
if(e[i].a==0){
ss[i]=abs(e[i].b);
}
if(e[i].a<0)e[i].a=-e[i].a,e[i].b=-e[i].b;
A[i]=e[i].a,B[i]=e[i].b;
}
sort(e+1,e+n+1);
map<pair<int,int>,int>mp;
for(int i=1;i<=n;++i)mp[make_pair(e[i].a,e[i].b)]=i;
long long he=0;
long long gs=0;
for(int i=1;i<=n;++i){
he+=ss[i];
gs+=A[i];
int wz=mp[make_pair(A[i],B[i])];
add(1,n,1,wz,A[i]);
int df=query(1,n,1,(gs+1)/2);
printf("%.10f\n",he+query2(1,n,1,df,1.0*e[df].b/e[df].a));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 11988kb
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.0000000000 82310.6896327239 86210.4524605675 117511.8811272270 213287.6227488254 245465.2130592321 248846.3927016246 345182.5276914641 445820.7672003182 456415.4090659842 553014.9941294742 555508.8207016676 609095.4250540282 627287.5359509925 634829.7809888037 691329.7679062765 751826.7525189880 8...
result:
wrong answer 2nd numbers differ - expected: '21040.3674840', found: '82310.6896327', error = '2.9120367'