QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#21333#2822. 不等式WhybullYMe#AC ✓1087ms34480kbC++142.6kb2022-03-04 15:58:112022-05-08 02:53:41

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 02:53:41]
  • 评测
  • 测评结果:AC
  • 用时:1087ms
  • 内存:34480kb
  • [2022-03-04 15:58:11]
  • 提交

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;
}

详细

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