QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#21678#2822. 不等式lindongli2004#AC ✓1006ms41456kbC++171.5kb2022-03-07 23:20:252022-05-08 03:54:45

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:54:45]
  • 评测
  • 测评结果:AC
  • 用时:1006ms
  • 内存:41456kb
  • [2022-03-07 23:20:25]
  • 提交

answer

#include<bits/stdc++.h>
#define re register
#define db double
#define LL long long
const int maxn=5e5+5;
inline int read() {
	char c=getchar();int x=0,r=1;while(c<'0'||c>'9'){if(c=='-')r=-1;c=getchar();}
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48,c=getchar();return x*r;
}
int a[maxn],b[maxn],id[maxn],pos[maxn],p[maxn],n;
int l[maxn*3],r[maxn*3];LL sa[maxn*3],sb[maxn*3],sum;
inline int cmp(int A,int B) {return 1ll*b[A]*a[B]>1ll*b[B]*a[A];}
void build(int x,int y,int i){
	l[i]=x,r[i]=y;if(x==y){p[x]=i;return;}
	int mid=x+y>>1;build(x,mid,i<<1),build(mid+1,y,i<<1|1);
}
inline void chg(int x,int va,int vb) {x=p[x];while(x)sa[x]+=va,sb[x]+=vb,x>>=1;}
int fid(int i,LL nw) {
	if(l[i]==r[i])return l[i];
	return sa[i<<1]>=nw?fid(i<<1,nw):fid(i<<1|1,nw-sa[i<<1]);
}
LL qry(int x,int y,int i,int o) {
	if(x<=l[i]&&y>=r[i]) return !o?sa[i]:sb[i];
	int mid=l[i]+r[i]>>1;LL tot=0;
	tot=(x<=mid?qry(x,y,i<<1,o):0)+(y>mid?qry(x,y,i<<1|1,o):0);
	return tot;
} 
int main() {
	n=read();for(re int i=1;i<=n;i++)a[i]=read();for(re int i=1;i<=n;i++)b[i]=read();
	for(re int i=1;i<=n;i++)if(a[i]<0)a[i]=-a[i],b[i]=-b[i];
	for(re int i=1;i<=n;i++)id[i]=i;std::sort(id+1,id+n+1,cmp);
	for(re int i=1;i<=n;i++)pos[id[i]]=i;build(1,n,1);
	for(re int t,i=1;i<=n;i++) {
		chg(pos[i],a[i],-b[i]);t=fid(1,((sum+=a[i])+1)>>1);
		db pnw=(db)(b[id[t]])/(db)(-a[id[t]]),ans=0;
		ans=(db)qry(1,t,1,0)*pnw-qry(1,t,1,1)+qry(t,n,1,1)-(db)qry(t,n,1,0)*pnw;
		printf("%.10lf\n",ans);
	}
	return 0;
}

詳細信息

Test #1:

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

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: 0
Accepted
time: 964ms
memory: 41456kb

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:

ok 500000 numbers

Test #3:

score: 0
Accepted
time: 4ms
memory: 16056kb

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.5134124532
238356.0617346855
295364.9250834141
346368.6077809372
431636.9138245591
450419.4667047248
471618.4897672622
531798.9483360758
637242.2067732294
774871.3276244638
829664.1624398022
859853.6971614537
902210.1261382505
949635.0573276239
9...

result:

ok 1000 numbers

Test #4:

score: 0
Accepted
time: 4ms
memory: 15976kb

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.3798789161
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: 16140kb

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.4451623272
488304.9002012856
566540.0147393027
579573.3690020128
580515.3804915254
631295.8178689695
707118.5192372880
730376.3780338983
7...

result:

ok 1000 numbers

Test #6:

score: 0
Accepted
time: 4ms
memory: 16144kb

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.6146756337
245299.4394010958
308349.5161534102
353626.8727564708
394683.7564489238
419007.3361308331
422091.9516102591
474747.1002416590
539590.7260994620
625609.9118343989
679560.3565520633
68...

result:

ok 1000 numbers

Test #7:

score: 0
Accepted
time: 983ms
memory: 40996kb

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.8885379543
503355.1502379479
516494.5300377618
536519.1542904519
601184.3387038829
670156.7675579931
7...

result:

ok 500000 numbers

Test #8:

score: 0
Accepted
time: 973ms
memory: 40240kb

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.7611773675
414428.2574198116
438180.3285138594
476341.8163698742
601570.8668790503
628142.5845722377
734786.3400566254
787860.2770433114
841679.2525345623
910414.8275510205
91...

result:

ok 500000 numbers

Test #9:

score: 0
Accepted
time: 945ms
memory: 40024kb

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.6504854369
356899.4604954805
402480.6998472937
407965.7133080708
411359.5565419596
490718.0601332189
587402.8791793891
664390.4568994556
691538.7471992525
767762.1184735247
850199.8232187680
900176.5389610389
...

result:

ok 500000 numbers

Test #10:

score: 0
Accepted
time: 1006ms
memory: 39952kb

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.0676988242
583004.8725626232
656827.2247181342
712839.6828470608
830963.6435820896
862170.7733023496
8...

result:

ok 500000 numbers