QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#21689 | #2822. 不等式 | lindongli2004 | AC ✓ | 1633ms | 174556kb | C++17 | 2.8kb | 2022-03-08 08:35:19 | 2022-05-08 03:56:43 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int N=1002021,eps=1e-17;
int n,sz,a[N],b[N],id[N<<3]; double stk[N*3],loc[N];
struct Tr{int w,f,_f,mi;}tr[N<<3];
void pushr(int x,int w,int _w){
tr[x].w+=_w; tr[x].f+=w; tr[x]._f+=_w; tr[x].mi+=w;
}
void down(int k){
if(tr[k].f || tr[k]._f){pushr(k<<1,tr[k].f,tr[k]._f); pushr(k<<1|1,tr[k].f,tr[k]._f); tr[k].f=tr[k]._f=0;}
}
double F(int k){
if(k<1 || k>sz)return 4e18;
// cerr<<"F "<<k<<" : "<<stk[k]<<" "<<tr[id[k]].w<<endl;
return stk[k]*1.0*tr[id[k]].mi+1.0*tr[id[k]].w;
}
int query(int k,int l,int r){
// cout<<"query "<<k<<" "<<l<<" "<<r<<" "<<tr[k].w<<endl;
if(l==r)return l;
// {
// cerr<<stk[l]<<" "<<tr[k].w<<endl;
// return stk[l]*1.0*tr[k].w;
// }
down(k);
int mid=(l+r)>>1;
if(tr[k<<1|1].mi>0)
return query(k<<1,l,mid);
else return query(k<<1|1,mid+1,r);
}
void change(int k,int l,int r,int ql,int qr,int ad,int ab){
if(ql<=l && qr>=r)return pushr(k,ad,ab);
down(k); int mid=(l+r)>>1;
if(ql<=mid)change(k<<1,l,mid,ql,qr,ad,ab);
if(qr>mid)change(k<<1|1,mid+1,r,ql,qr,ad,ab);
// tr[k].w=tr[k<<1].w+tr[k<<1|1].w;
tr[k].mi=min(tr[k<<1].mi,tr[k<<1|1].mi);
}
void build(int k,int l,int r){
if(l==r)return id[l]=k,void();
int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r);
}
void pushdown(int k,int l,int r,int x){
if(x<1 || x>sz)return;
if(l==r)return;
down(k); int mid=(l+r)>>1;
(x<=mid)?pushdown(k<<1,l,mid,x):pushdown(k<<1|1,mid+1,r,x);
tr[k].mi=min(tr[k<<1].mi,tr[k<<1|1].mi);
}
int read(){
int x=0,f=1; char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
#undef int
int main()
{
// freopen("I.in","r",stdin);
// freopen("I.out","w",stdout);
#define int long long
n=read(); int sumb=0,top=0;
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)b[i]=read();
for(int i=1;i<=n;i++)
if(a[i]<0)a[i]=-a[i],b[i]=-b[i];
for(int i=1;i<=n;i++){
loc[i]=1.0*(-b[i])/(1.0*a[i]);
stk[++top]=loc[i]-(1e-14),stk[++top]=loc[i],stk[++top]=loc[i]+(1e-14);
}
sort(stk+1,stk+top+1);
sz=unique(stk+1,stk+top+1)-(stk+1);
// cerr<<"sz="<<sz<<endl;
// for(int i=1;i<=sz;i++)
// printf("%0.10lf\n",stk[i]);
build(1,1,sz);
for(int i=1;i<=n;i++){
sumb+=b[i];
loc[i]=lower_bound(stk+1,stk+sz+1,loc[i])-stk;
change(1,1,sz,1,loc[i],-a[i],-b[i]);
change(1,1,sz,loc[i]+1,sz,a[i],b[i]);
// cerr<<"change "<<loc[i]<<endl;
int res=query(1,1,sz);
// printf("%0.20lf %0.20lf\n",F(res),F(res+1));
pushdown(1,1,sz,res+1); pushdown(1,1,sz,res-1);
// cerr<<res<<" "<<stk[res]<<" "<<stk[res+1]<<endl;
printf("%0.8lf\n",min(F(res-1),min(F(res),F(res+1))));
}
return 0;
}
/*
10
3 5 1 1 2 3 1 4 3 4
1 3 1 1 1 2 2 1 1 4
5
3 5 1 1 2
1 3 1 1 1
*/
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 14292kb
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: 1533ms
memory: 174544kb
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: 3ms
memory: 14192kb
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: 14184kb
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: 11ms
memory: 16108kb
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: 8ms
memory: 14208kb
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 8324...
result:
ok 1000 numbers
Test #7:
score: 0
Accepted
time: 1560ms
memory: 174448kb
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: 1618ms
memory: 174424kb
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: 1633ms
memory: 174556kb
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: 1569ms
memory: 174272kb
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