QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21331#2822. 不等式WhybullYMe#WA 956ms24716kbC++142.5kb2022-03-04 15:53:212022-05-08 02:53:35

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:35]
  • 评测
  • 测评结果:WA
  • 用时:956ms
  • 内存:24716kb
  • [2022-03-04 15:53:21]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
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;
}
int 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+n+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: 6ms
memory: 11936kb

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: -100
Wrong Answer
time: 956ms
memory: 24716kb

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:

wrong answer 42967th numbers differ - expected: '2137104979.5853341', found: '-197441070751160.0000000', error = '92388.1651778'