QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21294#2822. 不等式gsh#WA 765ms25968kbC++201.2kb2022-03-04 14:42:502022-05-08 02:50:49

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:50:49]
  • 评测
  • 测评结果:WA
  • 用时:765ms
  • 内存:25968kb
  • [2022-03-04 14:42:50]
  • 提交

answer

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define FOR(i,l,r) for(int i=l;i>=r;i--)
#define lowbit(x) x&-x
#define MAXN 1000001
int N,a[MAXN],b[MAXN],p[MAXN],q[MAXN];double x[MAXN],sa[MAXN],sb[MAXN];
int get(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;}
void upd(int x,double v1,double v2){for(int i=x;i<=N;i+=lowbit(i))sa[i]+=v1,sb[i]+=v2;}
double ask1(int x){double ans=0;for(int i=x;i;i-=lowbit(i))ans+=sa[i];return ans;}
double ask2(int x){double ans=0;for(int i=x;i;i-=lowbit(i))ans+=sb[i];return ans;}
int main()
{
	N=get();For(i,1,N)a[i]=get();For(i,1,N)b[i]=get(),x[i]=-1.0*b[i]/a[i];
	For(i,1,N)p[i]=i;sort(p+1,p+N+1,[&](int a,int b){return x[a]<x[b];});For(i,1,N)q[p[i]]=i;
	double s=0;
	For(i,1,N)
	{
		if(a[i]>0)upd(1,-a[i],-b[i]),upd(q[i],2*a[i],2*b[i]);else if(a[i]<0)upd(1,a[i],b[i]),upd(q[i],-2*a[i],-2*b[i]);else s+=b[i];
		int l=1,r=N;while(l<r){int mid=l+r>>1;if(ask1(mid)>0)r=mid;else l=mid+1;}
		double a=ask1(l),b=ask2(l);printf("%.10lf\n",a*x[p[l]]+b+s);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 14020kb

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.2670237435
622459.0320715895
625160.8650837715
633787.7989086842
654740.7191612910
679518.0803346169
7...

result:

ok 1000 numbers

Test #2:

score: -100
Wrong Answer
time: 765ms
memory: 25968kb

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.2016268008
183734.7840352933
249323.8172676764
322652.8750749311
323189.0759991496
351287.6426262754
410937.4178127046
460816.5299026132
493996.4337832985
550307.8996979108
578503.9449268015
601978.5788929482
638641.1839575807
6...

result:

wrong answer 156720th numbers differ - expected: '7845248160.4640989', found: '7845217104.4640989', error = '0.0000040'