QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#21331 | #2822. 不等式 | WhybullYMe# | WA | 956ms | 24716kb | C++14 | 2.5kb | 2022-03-04 15:53:21 | 2022-05-08 02:53:35 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,a[500001],b[500001],cnt,sum[500001<<2],qwq,qaq;
double node[500001],ans[500001<<2];
inline int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline int ls(int k)
{
return k<<1;
}
inline int rs(int k)
{
return k<<1|1;
}
inline void push_up(int k)
{
sum[k]=sum[ls(k)]+sum[rs(k)];
ans[k]=ans[ls(k)]+ans[rs(k)];
}
inline void update(int node,int l,int r,int k,int p1,double p2)
{
if(l==r)
{
sum[k]+=p1;
ans[k]+=p1*p2;
return;
}
int mid=(l+r)>>1;
if(node<=mid)
update(node,l,mid,ls(k),p1,p2);
else
update(node,mid+1,r,rs(k),p1,p2);
push_up(k);
}
inline int query1(int l,int r,int k,int p)
{
if(l==r)
return l;
int mid=(l+r)>>1;
if(p<=sum[ls(k)])
return query1(l,mid,ls(k),p);
return query1(mid+1,r,rs(k),p-sum[ls(k)]);
}
inline int query2(int nl,int nr,int l,int r,int k)
{
if(nl>nr)
return 0;
if(l>=nl&&r<=nr)
return sum[k];
int mid=(l+r)>>1,res=0;
if(nl<=mid)
res+=query2(nl,nr,l,mid,ls(k));
if(nr>mid)
res+=query2(nl,nr,mid+1,r,rs(k));
return res;
}
inline double query3(int nl,int nr,int l,int r,int k)
{
if(nl>nr)
return 0.0000;
if(l>=nl&&r<=nr)
return ans[k];
int mid=(l+r)>>1;
double res=0;
if(nl<=mid)
res+=query3(nl,nr,l,mid,ls(k));
if(nr>mid)
res+=query3(nl,nr,mid+1,r,rs(k));
return res;
}
int main()
{
n=read();
for(int i=1;i<=n;++i)
a[i]=read();
for(int i=1;i<=n;++i)
{
b[i]=read();
if(a[i])
node[++cnt]=-1.0*b[i]/a[i];
}
sort(node+1,node+cnt+1);
cnt=unique(node+1,node+n+1)-node-1;
for(int i=1;i<=n;++i)
{
if(!a[i])
qwq+=abs(b[i]);
else
{
int pos=lower_bound(node+1,node+cnt+1,-1.0*b[i]/a[i])-node;
update(pos,1,cnt,1,abs(a[i]),-1.0*b[i]/a[i]);
qaq+=abs(a[i]);
}
int tmp=query1(1,cnt,1,(qaq+1)>>1);
printf("%.10lf\n",qwq+node[tmp]*query2(1,tmp-1,1,cnt,1)-query3(1,tmp-1,1,cnt,1)-node[tmp]*query2(tmp+1,cnt,1,cnt,1)+query3(tmp+1,cnt,1,cnt,1));
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 6ms
memory: 11936kb
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 21040.3674842418 46739.8011692087 118552.3871778961 134885.2909243390 138647.7562118980 181413.0968851807 262021.9724859419 332218.4892212414 448697.7365037040 526654.9827231457 604758.2670237434 622459.0320715895 625160.8650837715 633787.7989086842 654740.7191612910 679518.0803346168 7...
result:
ok 1000 numbers
Test #2:
score: -100
Wrong Answer
time: 956ms
memory: 24716kb
input:
500000 72535 50164 -41705 -27256 99923 -47337 -84129 -19076 -28224 47616 20591 30941 35900 -30965 1834 -33114 62440 56631 -45421 84047 77094 -86440 30282 -60892 44910 89786 -566 -87476 60388 13980 63363 91246 10736 59064 7550 30290 -68811 73956 90454 6060 76719 -58321 66048 -6321 -39195 24249 -20336...
output:
0.0000000000 60376.9402357483 66670.5308476202 164077.4140990289 182310.2016268009 183734.7840352933 249323.8172676764 322652.8750749311 323189.0759991496 351287.6426262754 410937.4178127046 460816.5299026131 493996.4337832985 550307.8996979108 578503.9449268015 601978.5788929482 638641.1839575807 6...
result:
wrong answer 42967th numbers differ - expected: '2137104979.5853341', found: '-197441070751160.0000000', error = '92388.1651778'