QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#420294#2822. 不等式300_205_205#AC ✓535ms39112kbC++143.6kb2024-05-24 16:15:252024-05-24 16:15:25

Judging History

你现在查看的是最新测评结果

  • [2024-05-24 16:15:25]
  • 评测
  • 测评结果:AC
  • 用时:535ms
  • 内存:39112kb
  • [2024-05-24 16:15:25]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define rg register
#define ll long long
#define ull unsigned ll
#define lowbit(x) (x&(-x))
#define djq 59393
const double eps=1e-10;
const short sint=0x3f3f;
const int inf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;
const double alpha=0.73;
const double PI=acos(-1);
inline void file(){
	freopen("entrench.in","r",stdin);
	freopen("entrench.out","w",stdout);
}
inline ll read(){
	rg ll ret=0,f=0;char ch=getchar();
    while(!isdigit(ch)){if(ch==EOF)exit(0);if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+ch-48;ch=getchar();}
    return f?-ret:ret;
}

#define ep emplace
#define epb emplace_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define it iterator
#define mkp make_pair
#define naive return 0*puts("Yes")
#define angry return 0*puts("No")
#define fls fflush(stdout)
#define rep(i,x,y) for(rg int i=(x);i<=(y);++i)
#define per(i,x,y) for(rg int i=(x);i>=(y);--i)
#define rep0(i,a) for(rg int i=0;i<=a;++i)
#define per0(i,a) for(rg int i=a;~i;--i)
#define szf sizeof
typedef vector<int> vec;
typedef pair<int,int> pii;
struct point{ int x,y; point(int x=0,int y=0):x(x),y(y) {} inline bool operator<(const point& T)const{ return x^T.x?x<T.x:y<T.y; }; };
inline int ksm(int base,int p){int ret=1;while(p){if(p&1)ret=1ll*ret*base%djq;base=1ll*base*base%djq,p>>=1;}return ret;}
inline void pls(int& x,const int k){ x=(x+k>=djq?x+k-djq:x+k); }
inline int add(const int a,const int b){ return a+b>=djq?a+b-djq:a+b; }
inline void sub(int& x,const int k){ x=(x-k<0?x-k+djq:x-k); }
inline int inc(const int a,const int b){ return a<b?a-b+djq:a-b; }
inline void ckmn(int& x,const int k){ x=(k<x?k:x); }
inline void ckmx(int& x,const int k){ x=(k>x?k:x); }
inline void ckmn(ll& x,const ll k){ x=(k<x?k:x); }
inline void ckmx(ll& x,const ll k){ x=(k>x?k:x); }
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


struct func{
	ll x,y;
	func(ll x=0,ll y=0):x(x),y(y) {}
};
const func Z=func(0,0);
inline func operator+(func x,func y){ return func(x.x+y.x,x.y+y.y); }
inline func operator-(func x,func y){ return func(x.x-y.x,x.y-y.y); }
int n,m,a[500005],b[500005],pos[500005];
pair<pii,int> c[500005];
func v[500005][2],all;
ll ex;
	func bit[500005];
	inline void ad(int x,const func k){
		while(x<=m) bit[x]=bit[x]+k,x+=(x&(-x));
	}
	inline func qr(int x){
		func res=Z;
		while(x) res=res+bit[x],x-=(x&(-x));
		return res;
	}

inline double gv(int x){
	func f1=qr(x),f0=Z-(all-f1),res=f1+f0;
	double vx=(double)c[x].fi.fi/(double)c[x].fi.se;
	//printf("vx=%.6lf k=%lld b=%lld\n",vx,res.x,res.y);
	return vx*res.x+res.y;
}
signed main(){
//	file();
	n=read();
	rep(i,1,n) a[i]=read();
	rep(i,1,n) b[i]=read();
	rep(i,1,n){
		func nv=func(a[i],b[i]);
		pii nw;
		nw.fi=-b[i],nw.se=a[i];
		if(a[i]==0) continue;
		if(a[i]<0) nw.se=-nw.se,nw.fi=-nw.fi;
		c[++m]=mkp(nw,i);
		if(a[i]>0) v[i][1]=nv,v[i][0]=Z-nv;
		else v[i][0]=nv,v[i][1]=Z-nv;
	}
	sort(c+1,c+1+m,[&](const pair<pii,int>& x,const pair<pii,int>& y){
		return 1ll*x.fi.fi*y.fi.se<1ll*y.fi.fi*x.fi.se;	
	});
	rep(i,1,m) pos[c[i].se]=i;
	//rep(i,1,m) printf("(%d/%d) %d\n",c[i].fi.fi,c[i].fi.se,c[i].se);
	all=Z;
	rep(i,1,n){
		if(a[i]==0){
			ex+=abs(b[i]);
		}else{
			all=all+v[i][1];
			ad(pos[i],v[i][1]);
		}
		int l=1,r=m;
		double ans=gv(l);
		while(l<r){
			const int mid=(l+r+1)/2;
			double v1=gv(mid),v0=gv(mid-1);
			if(v1<=v0) l=mid,ans=min(ans,v1);
			else r=mid-1;
		}
		ans+=ex;
		printf("%.8lf\n",ans);
	}
	return 0; 
}
/*

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 35352kb

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.00000000
21040.36748424
46739.80116921
118552.38717790
134885.29092434
138647.75621190
181413.09688518
262021.97248594
332218.48922124
448697.73650370
526654.98272315
604758.26702374
622459.03207159
625160.86508377
633787.79890868
654740.71916129
679518.08033462
721477.04651084
781941.45609318
792...

result:

ok 1000 numbers

Test #2:

score: 0
Accepted
time: 521ms
memory: 39008kb

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.00000000
60376.94023575
66670.53084762
164077.41409903
182310.20162680
183734.78403529
249323.81726768
322652.87507493
323189.07599915
351287.64262628
410937.41781270
460816.52990261
493996.43378330
550307.89969791
578503.94492680
601978.57889295
638641.18395758
676441.88346797
708724.77208968
710...

result:

ok 500000 numbers

Test #3:

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

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.00000000
29129.99190188
68274.97203707
225727.51341245
238356.06173469
295364.92508341
346368.60778094
431636.91382456
450419.46670472
471618.48976726
531798.94833608
637242.20677323
774871.32762446
829664.16243980
859853.69716145
902210.12613825
949635.05732762
992598.22728095
1071512.19234466
11...

result:

ok 1000 numbers

Test #4:

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

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.00000000
2790.11768702
26580.61749760
28434.70087729
31900.80853514
33196.37987892
72675.25924807
234209.46744452
296648.28091561
360573.08235075
361893.62327788
474454.22236502
629188.66388585
702715.57905714
827378.25818242
848383.00460487
871521.98511161
1003754.22161191
1110723.00623619
122904...

result:

ok 1000 numbers

Test #5:

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

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.00000000
54514.37240537
80128.40158846
141290.83650948
233404.28089210
269382.00234927
318600.40926724
319893.72172935
401340.74264695
451697.44516233
488304.90020129
566540.01473930
579573.36900201
580515.38049153
631295.81786897
707118.51923729
730376.37803390
735772.27542373
824388.94261017
883...

result:

ok 1000 numbers

Test #6:

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

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.00000000
42465.01509081
47133.94962495
49347.91477245
158118.78864642
205540.61571887
207566.61467563
245299.43940110
308349.51615341
353626.87275647
394683.75644892
419007.33613083
422091.95161026
474747.10024166
539590.72609946
625609.91183440
679560.35655206
680641.09297161
741204.16344019
832...

result:

ok 1000 numbers

Test #7:

score: 0
Accepted
time: 515ms
memory: 39064kb

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.00000000
64218.17741532
80783.80787256
111354.61190952
113899.53632825
161635.84803622
173883.03854813
262132.41808393
267176.46335495
268395.41739130
389285.33741784
458350.88853795
503355.15023795
516494.53003776
536519.15429045
601184.33870388
670156.76755799
724582.69075584
806292.38991295
847...

result:

ok 500000 numbers

Test #8:

score: 0
Accepted
time: 523ms
memory: 39032kb

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.00000000
78956.43033163
81831.18187987
87237.59366661
199764.81243419
276005.73404778
286092.40475413
369929.76117737
414428.25741981
438180.32851386
476341.81636987
601570.86687905
628142.58457224
734786.34005663
787860.27704331
841679.25253456
910414.82755102
913285.95383391
950559.76757735
9741...

result:

ok 500000 numbers

Test #9:

score: 0
Accepted
time: 535ms
memory: 39068kb

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.00000000
19538.38668075
140900.82064550
192720.21409441
249702.18898560
295603.65048544
356899.46049548
402480.69984729
407965.71330807
411359.55654196
490718.06013322
587402.87917939
664390.45689946
691538.74719925
767762.11847352
850199.82321877
900176.53896104
960011.09920906
1017615.51635582
1...

result:

ok 500000 numbers

Test #10:

score: 0
Accepted
time: 523ms
memory: 39112kb

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.00000000
34042.58891155
74440.64537313
112133.25310210
180044.83581502
182665.32223083
207636.71176521
278710.71262587
353875.96652035
515444.13977106
554250.83854032
556211.06769882
583004.87256262
656827.22471813
712839.68284706
830963.64358209
862170.77330235
889145.43351407
920071.46553060
928...

result:

ok 500000 numbers