QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#21407#2822. 不等式qingyu_orz#AC ✓1884ms62172kbC++201.6kb2022-03-04 20:07:372022-05-08 03:12:33

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 03:12:33]
  • 评测
  • 测评结果:AC
  • 用时:1884ms
  • 内存:62172kb
  • [2022-03-04 20:07:37]
  • 提交

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",&e[i].a);
	for(int i=1;i<=n;++i)scanf("%d",&e[i].b);
	for(int i=1;i<=n;++i){
		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;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 14092kb

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.9724859420
332218.4892212414
448697.7365037040
526654.9827231457
604758.2670237435
622459.0320715896
625160.8650837716
633787.7989086841
654740.7191612909
679518.0803346171
7...

result:

ok 1000 numbers

Test #2:

score: 0
Accepted
time: 1871ms
memory: 61372kb

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.0759991497
351287.6426262754
410937.4178127046
460816.5299026131
493996.4337832985
550307.8996979108
578503.9449268015
601978.5788929482
638641.1839575808
6...

result:

ok 500000 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 14188kb

input:

1000
-10425 -17041 36906 59558 -60841 -7805 31449 14104 85461 50561 11774 -20252 93500 58651 -57215 -37974 -19429 58555 63645 15237 90613 89871 78596 42579 -22620 64026 -81175 -38726 -49550 -32689 15165 92873 -16518 -83443 -59029 23471 -74111 -98979 -82859 -3338 -1030 83309 46000 3043 -78665 72668 -...

output:

0.0000000000
29129.9919018837
68274.9720370671
225727.5134124533
238356.0617346855
295364.9250834141
346368.6077809372
431636.9138245591
450419.4667047249
471618.4897672622
531798.9483360758
637242.2067732295
774871.3276244638
829664.1624398022
859853.6971614537
902210.1261382505
949635.0573276238
9...

result:

ok 1000 numbers

Test #4:

score: 0
Accepted
time: 7ms
memory: 14016kb

input:

1000
-61825 -50967 96854 79449 67720 25513 30223 -79637 -51388 -32693 83255 -24889 -65899 -12087 -68993 46694 -8115 34771 97971 95070 60311 -58812 7269 -48380 -11935 -58285 68563 76645 47700 -81487 12769 -85920 -51948 -60010 70982 -52948 2782 86662 -91091 86941 -90638 -29034 6669 53496 -37180 -31106...

output:

0.0000000000
2790.1176870198
26580.6174975965
28434.7008772923
31900.8085351447
33196.3798789160
72675.2592480711
234209.4674445242
296648.2809156117
360573.0823507548
361893.6232778812
474454.2223650231
629188.6638858488
702715.5790571376
827378.2581824189
848383.0046048692
871521.9851116113
100375...

result:

ok 1000 numbers

Test #5:

score: 0
Accepted
time: 3ms
memory: 12140kb

input:

1000
64701 12956 98586 54145 -79377 8893 22728 62220 -94794 92406 71653 -43144 42708 -59000 -96943 -60145 18033 -77522 20852 -62583 -68415 6199 -77462 -77694 -36011 -80297 -94508 -33000 49541 -29509 -11838 78222 -28841 -66724 38255 -53453 30240 -13672 -22140 23630 43841 19604 64885 35473 -5664 -3885...

output:

0.0000000000
54514.3724053724
80128.4015884608
141290.8365094821
233404.2808921037
269382.0023492682
318600.4092672447
319893.7217293475
401340.7426469452
451697.4451623273
488304.9002012856
566540.0147393027
579573.3690020129
580515.3804915254
631295.8178689696
707118.5192372880
730376.3780338983
7...

result:

ok 1000 numbers

Test #6:

score: 0
Accepted
time: 7ms
memory: 14200kb

input:

1000
48175 12749 -61459 39318 87673 84688 53381 99380 -41961 74090 81458 20797 -67101 -61294 -93637 30002 31575 64837 82148 -93582 85834 -55522 82400 -75251 83169 -99328 -35842 33732 63856 93931 -19563 -6035 -75307 52896 -60812 -2658 7096 -8073 -52671 33232 -86272 -20335 -83582 8235 56187 -1369 -912...

output:

0.0000000000
42465.0150908147
47133.9496249532
49347.9147724499
158118.7886464215
205540.6157188740
207566.6146756336
245299.4394010958
308349.5161534102
353626.8727564708
394683.7564489238
419007.3361308331
422091.9516102591
474747.1002416590
539590.7260994620
625609.9118343990
679560.3565520634
68...

result:

ok 1000 numbers

Test #7:

score: 0
Accepted
time: 1805ms
memory: 62172kb

input:

500000
-37274 -91965 47525 24618 57211 23151 8445 -54498 46859 82915 -94092 67940 20006 -43695 -36185 51956 16227 26339 -16412 38957 53689 19558 55085 83943 -65052 -99026 -68516 35326 23942 -23495 -66467 80839 22808 4310 -950 -49236 -87106 -58402 99240 27427 33345 -14321 -72696 -9090 18213 -33266 -2...

output:

0.0000000000
64218.1774153210
80783.8078725602
111354.6119095213
113899.5363282483
161635.8480362168
173883.0385481326
262132.4180839349
267176.4633549493
268395.4173913043
389285.3374178375
458350.8885379544
503355.1502379479
516494.5300377617
536519.1542904519
601184.3387038829
670156.7675579931
7...

result:

ok 500000 numbers

Test #8:

score: 0
Accepted
time: 1819ms
memory: 61496kb

input:

500000
-60760 -63142 42737 -73452 -39875 -29298 67663 13222 -88683 98557 -69983 -71005 10596 -54666 44321 57640 34829 -42363 -83245 88161 48592 -53081 -69849 -48359 61001 -10142 8855 8965 59304 -93058 56898 -32157 -24518 -67057 6052 70990 96221 36755 1032 79249 8353 -89123 -95344 -4813 -22499 26620 ...

output:

0.0000000000
78956.4303316335
81831.1818798699
87237.5936666122
199764.8124341905
276005.7340477806
286092.4047541252
369929.7611773676
414428.2574198116
438180.3285138594
476341.8163698742
601570.8668790504
628142.5845722377
734786.3400566254
787860.2770433115
841679.2525345624
910414.8275510204
91...

result:

ok 500000 numbers

Test #9:

score: 0
Accepted
time: 1864ms
memory: 61616kb

input:

500000
-75755 17681 32965 95584 20522 26879 -21149 -92029 -2086 40964 -19043 10276 -42053 -50450 55781 26443 -79949 31685 28162 -5736 42789 -55511 636 79200 -59234 -7548 -39416 -73589 -50508 53398 50090 85561 83874 69308 -77780 -99287 -7813 99321 24617 78381 61382 81411 -25601 39173 -80308 39802 988...

output:

0.0000000000
19538.3866807471
140900.8206455020
192720.2140944091
249702.1889856043
295603.6504854368
356899.4604954804
402480.6998472937
407965.7133080708
411359.5565419596
490718.0601332189
587402.8791793890
664390.4568994555
691538.7471992522
767762.1184735247
850199.8232187680
900176.5389610389
...

result:

ok 500000 numbers

Test #10:

score: 0
Accepted
time: 1884ms
memory: 61740kb

input:

500000
20100 21572 -35594 -41343 -52497 69714 14056 32038 18275 75066 59060 82158 13876 -24420 83116 65764 58785 46635 9591 -66193 79246 -63255 -35359 90131 -36034 -90826 -52404 -62961 9477 -65632 21897 -44243 -27123 -20830 71616 -48715 77470 36530 -76765 46815 -62284 8069 38405 -76046 -11175 -248 -...

output:

0.0000000000
34042.5889115520
74440.6453731343
112133.2531020971
180044.8358150250
182665.3222308288
207636.7117652122
278710.7126258714
353875.9665203546
515444.1397710646
554250.8385403219
556211.0676988243
583004.8725626232
656827.2247181342
712839.6828470608
830963.6435820895
862170.7733023496
8...

result:

ok 500000 numbers