QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21445#2822. 不等式WhybullYMeAC ✓1167ms39744kbC++141.9kb2022-03-05 03:42:202022-05-08 03:28:34

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:28:34]
  • 评测
  • 测评结果:AC
  • 用时:1167ms
  • 内存:39744kb
  • [2022-03-05 03:42:20]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ri int
typedef long long ll;
const int maxn=5e5+10;
template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;}
template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;}
template<class T>inline void clear(T *arr,int siz,int val=0){memset(arr,val,sizeof(T)*(siz+1));}
int a[maxn],dl,n;
double b[maxn],d[maxn];
ll ex;
struct segment_tree{
	int l,r;
	ll cnt;
	double sum;
}t[maxn<<2];
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
inline void push_up(int p){
	t[p].cnt=t[ls(p)].cnt+t[rs(p)].cnt;
	t[p].sum=t[ls(p)].sum+t[rs(p)].sum;
}
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r)return;
	ri mid=l+r>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	push_up(p);
}
void modify(int p,int k,int v){
	if(t[p].l>k||k>t[p].r)return;
	if(t[p].l==t[p].r){
		t[p].cnt+=v;
		t[p].sum+=d[k]*v;
		return;
	}
	modify(ls(p),k,v);
	modify(rs(p),k,v);
	push_up(p);
}
double query(int p,int l,int r){
	if(t[p].l>r||l>t[p].r)return 0;
	if(l<=t[p].l&&t[p].r<=r)return t[p].sum;
	return query(ls(p),l,r)+query(rs(p),l,r);
}
ll query_(int p,int l,int r){
	if(t[p].l>r||l>t[p].r)return 0;
	if(l<=t[p].l&&t[p].r<=r)return t[p].cnt;
	return query_(ls(p),l,r)+query_(rs(p),l,r);
}
int kth(int p,ll k){
	if(t[p].l==t[p].r)return t[p].l;
	return t[ls(p)].cnt>=k?kth(ls(p),k):kth(rs(p),k-t[ls(p)].cnt);
}
int main(){
	scanf("%d",&n);
	for(ri i=1;i<=n;++i)scanf("%d",a+i);
	for(ri i=1;i<=n;++i){
		scanf("%lf",b+i);
		if(a[i])b[i]/=-a[i],d[++dl]=b[i];
	}
	sort(d+1,d+dl+1);
	dl=unique(d+1,d+dl+1)-d-1;
	build(1,1,dl);
	for(ri i=1;i<=n;++i){
		if(a[i])modify(1,lower_bound(d+1,d+dl+1,b[i])-d,abs(a[i]));
		else ex+=abs(b[i]);
		ll mid=t[1].cnt+1>>1;
		ri j=kth(1,mid);
		ll lc=query_(1,1,j);
		double ls=query(1,1,j);
		printf("%lf\n",lc*d[j]-ls+(t[1].sum-ls)-(t[1].cnt-lc)*d[j]+ex);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 9968kb

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.000000
21040.367484
46739.801169
118552.387178
134885.290924
138647.756212
181413.096885
262021.972486
332218.489221
448697.736504
526654.982723
604758.267024
622459.032072
625160.865084
633787.798909
654740.719161
679518.080335
721477.046511
781941.456093
792048.922083
806557.973974
862543.537689...

result:

ok 1000 numbers

Test #2:

score: 0
Accepted
time: 1167ms
memory: 38740kb

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.000000
60376.940236
66670.530848
164077.414099
182310.201627
183734.784035
249323.817268
322652.875075
323189.075999
351287.642626
410937.417813
460816.529903
493996.433783
550307.899698
578503.944927
601978.578893
638641.183958
676441.883468
708724.772090
710978.244006
721954.641796
748499.853058...

result:

ok 500000 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 9976kb

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.000000
29129.991902
68274.972037
225727.513412
238356.061735
295364.925083
346368.607781
431636.913825
450419.466705
471618.489767
531798.948336
637242.206773
774871.327624
829664.162440
859853.697161
902210.126138
949635.057328
992598.227281
1071512.192345
1170454.021078
1179617.064362
1203071.46...

result:

ok 1000 numbers

Test #4:

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

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.000000
2790.117687
26580.617498
28434.700877
31900.808535
33196.379879
72675.259248
234209.467445
296648.280916
360573.082351
361893.623278
474454.222365
629188.663886
702715.579057
827378.258182
848383.004605
871521.985112
1003754.221612
1110723.006236
1229046.555889
1322314.931316
1324817.944909...

result:

ok 1000 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 9968kb

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.000000
54514.372405
80128.401588
141290.836509
233404.280892
269382.002349
318600.409267
319893.721729
401340.742647
451697.445162
488304.900201
566540.014739
579573.369002
580515.380492
631295.817869
707118.519237
730376.378034
735772.275424
824388.942610
883545.344883
917485.420983
980643.551373...

result:

ok 1000 numbers

Test #6:

score: 0
Accepted
time: 6ms
memory: 9952kb

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.000000
42465.015091
47133.949625
49347.914772
158118.788646
205540.615719
207566.614676
245299.439401
308349.516153
353626.872756
394683.756449
419007.336131
422091.951610
474747.100242
539590.726099
625609.911834
679560.356552
680641.092972
741204.163440
832499.259352
861084.661376
909060.920746
...

result:

ok 1000 numbers

Test #7:

score: 0
Accepted
time: 1123ms
memory: 38236kb

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.000000
64218.177415
80783.807873
111354.611910
113899.536328
161635.848036
173883.038548
262132.418084
267176.463355
268395.417391
389285.337418
458350.888538
503355.150238
516494.530038
536519.154290
601184.338704
670156.767558
724582.690756
806292.389913
847823.747912
848240.456537
955418.588985...

result:

ok 500000 numbers

Test #8:

score: 0
Accepted
time: 1110ms
memory: 38108kb

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.000000
78956.430332
81831.181880
87237.593667
199764.812434
276005.734048
286092.404754
369929.761177
414428.257420
438180.328514
476341.816370
601570.866879
628142.584572
734786.340057
787860.277043
841679.252535
910414.827551
913285.953834
950559.767577
974178.530711
1033579.355760
1047552.64047...

result:

ok 500000 numbers

Test #9:

score: 0
Accepted
time: 1086ms
memory: 38748kb

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.000000
19538.386681
140900.820646
192720.214094
249702.188986
295603.650485
356899.460495
402480.699847
407965.713308
411359.556542
490718.060133
587402.879179
664390.456899
691538.747199
767762.118474
850199.823219
900176.538961
960011.099209
1017615.516356
1066634.177912
1083169.852101
1112136.0...

result:

ok 500000 numbers

Test #10:

score: 0
Accepted
time: 1105ms
memory: 39744kb

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.000000
34042.588912
74440.645373
112133.253102
180044.835815
182665.322231
207636.711765
278710.712626
353875.966520
515444.139771
554250.838540
556211.067699
583004.872563
656827.224718
712839.682847
830963.643582
862170.773302
889145.433514
920071.465531
928914.974439
936086.779011
960500.208036...

result:

ok 500000 numbers