QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#21333 | #2822. 不等式 | WhybullYMe# | AC ✓ | 1087ms | 34480kb | C++14 | 2.6kb | 2022-03-04 15:58:11 | 2022-05-08 02:53:41 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define int long long
int n,a[500001],b[500001],cnt,sum[500001<<2],qwq,qaq;
double node[500001],ans[500001<<2];
inline int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline int ls(int k)
{
return k<<1;
}
inline int rs(int k)
{
return k<<1|1;
}
inline void push_up(int k)
{
sum[k]=sum[ls(k)]+sum[rs(k)];
ans[k]=ans[ls(k)]+ans[rs(k)];
}
inline void update(int node,int l,int r,int k,int p1,double p2)
{
if(l==r)
{
sum[k]+=p1;
ans[k]+=p1*p2;
return;
}
int mid=(l+r)>>1;
if(node<=mid)
update(node,l,mid,ls(k),p1,p2);
else
update(node,mid+1,r,rs(k),p1,p2);
push_up(k);
}
inline int query1(int l,int r,int k,int p)
{
if(l==r)
return l;
int mid=(l+r)>>1;
if(p<=sum[ls(k)])
return query1(l,mid,ls(k),p);
return query1(mid+1,r,rs(k),p-sum[ls(k)]);
}
inline int query2(int nl,int nr,int l,int r,int k)
{
if(nl>nr)
return 0;
if(l>=nl&&r<=nr)
return sum[k];
int mid=(l+r)>>1,res=0;
if(nl<=mid)
res+=query2(nl,nr,l,mid,ls(k));
if(nr>mid)
res+=query2(nl,nr,mid+1,r,rs(k));
return res;
}
inline double query3(int nl,int nr,int l,int r,int k)
{
if(nl>nr)
return 0.0000;
if(l>=nl&&r<=nr)
return ans[k];
int mid=(l+r)>>1;
double res=0;
if(nl<=mid)
res+=query3(nl,nr,l,mid,ls(k));
if(nr>mid)
res+=query3(nl,nr,mid+1,r,rs(k));
return res;
}
signed main()
{
n=read();
for(int i=1;i<=n;++i)
a[i]=read();
for(int i=1;i<=n;++i)
{
b[i]=read();
if(a[i])
node[++cnt]=-1.0*b[i]/a[i];
}
sort(node+1,node+cnt+1);
cnt=unique(node+1,node+cnt+1)-node-1;
for(int i=1;i<=n;++i)
{
if(!a[i])
qwq+=abs(b[i]);
else
{
int pos=lower_bound(node+1,node+cnt+1,-1.0*b[i]/a[i])-node;
update(pos,1,cnt,1,abs(a[i]),-1.0*b[i]/a[i]);
qaq+=abs(a[i]);
}
int tmp=query1(1,cnt,1,(qaq+1)>>1);
printf("%.10lf\n",qwq+node[tmp]*query2(1,tmp-1,1,cnt,1)-query3(1,tmp-1,1,cnt,1)-node[tmp]*query2(tmp+1,cnt,1,cnt,1)+query3(tmp+1,cnt,1,cnt,1));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 11868kb
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: 1087ms
memory: 33568kb
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: 3ms
memory: 11936kb
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.9250834142 346368.6077809372 431636.9138245591 450419.4667047248 471618.4897672622 531798.9483360758 637242.2067732294 774871.3276244637 829664.1624398021 859853.6971614537 902210.1261382505 949635.0573276239 9...
result:
ok 1000 numbers
Test #4:
score: 0
Accepted
time: 3ms
memory: 11928kb
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: 11936kb
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.8178689695 707118.5192372880 730376.3780338983 7...
result:
ok 1000 numbers
Test #6:
score: 0
Accepted
time: 3ms
memory: 11932kb
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.9118343990 679560.3565520633 68...
result:
ok 1000 numbers
Test #7:
score: 0
Accepted
time: 1048ms
memory: 33396kb
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.3374178376 458350.8885379543 503355.1502379479 516494.5300377617 536519.1542904519 601184.3387038829 670156.7675579931 7...
result:
ok 500000 numbers
Test #8:
score: 0
Accepted
time: 1076ms
memory: 33284kb
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.8275510204 91...
result:
ok 500000 numbers
Test #9:
score: 0
Accepted
time: 1077ms
memory: 34480kb
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.4604954804 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: 1050ms
memory: 33840kb
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