QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#21279 | #2822. 不等式 | DaBenZhongXiaSongKuaiDi# | AC ✓ | 1172ms | 41728kb | C++20 | 1.7kb | 2022-03-04 14:26:10 | 2022-05-08 02:49:27 |
Judging History
answer
#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=5e5+10;
db a[N],b[N],Zero[N],v[N],S;
int n,z[N],len;
db tmp[N];
db sum[N<<2],s[N<<2];
#define lson (id<<1)
#define rson (id<<1|1)
#define mid ((l+r)>>1)
const db eps=1e-8;
void update(int id){
sum[id]=sum[lson]+sum[rson];
s[id]=s[lson]+s[rson];
}
void add(int id,int l,int r,int pos,db k1,db k2){
if(l==r){
sum[id]+=k1;
s[id]+=k2;
return;
}
if(pos<=mid) add(lson,l,mid,pos,k1,k2);
else add(rson,mid+1,r,pos,k1,k2);
update(id);
}
int Find(int id,int l,int r,db k){
if(l==r)return l;
if(sum[lson]>k||fabs(sum[lson]-k)<eps) return Find(lson,l,mid,k);
else return Find(rson,mid+1,r,k-sum[lson]);
}
db query1(int id,int l,int r,int L,int R){
if(r<L||R<l)return 0;
if(L<=l&&r<=R)return sum[id];
return query1(lson,l,mid,L,R)+query1(rson,mid+1,r,L,R);
}
db query2(int id,int l,int r,int L,int R){
if(r<L||R<l)return 0;
if(L<=l&&r<=R)return s[id];
return query2(lson,l,mid,L,R)+query2(rson,mid+1,r,L,R);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
for(int i=1;i<=n;i++) scanf("%lf",&b[i]);
for(int i=1;i<=n;i++){
v[i]=Zero[i]=-b[i]/a[i];
if(a[i]<0) a[i]=-a[i],b[i]=-b[i];
}
sort(v+1,v+1+n);
for(int i=1;i<=n;i++){
if(fabs(tmp[len]-v[i])>eps){
tmp[++len]=v[i];
}
}
memset(v,0.0,sizeof(v));
for(int i=1;i<=len;i++) v[i]=tmp[i];
for(int i=1;i<=n;i++) z[i]=lower_bound(v+1,v+1+len,Zero[i])-v;
for(int i=1;i<=n;i++){
add(1,1,len,z[i],a[i],b[i]);
S+=a[i];
int k=Find(1,1,len,S/2);
printf("%.6lf\n",v[k]*(query1(1,1,len,1,k-1)-query1(1,1,len,k+1,len))-query2(1,1,len,k+1,len)+query2(1,1,len,1,k-1));
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 18140kb
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: 1031ms
memory: 41668kb
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: 4ms
memory: 18156kb
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: 1ms
memory: 16092kb
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: 2ms
memory: 18152kb
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: 9ms
memory: 18288kb
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: 1113ms
memory: 41728kb
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: 1144ms
memory: 41596kb
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: 1172ms
memory: 41692kb
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: 1074ms
memory: 41668kb
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.326376 207636.727388 278710.702087 353875.970904 515444.082859 554250.829855 556211.067699 583004.872563 656827.274510 712839.664769 830963.643582 862170.749526 889145.447818 920071.487666 928914.974439 936086.779011 960500.208036...
result:
ok 500000 numbers