QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#21676 | #2822. 不等式 | lindongli2004# | WA | 3ms | 14220kb | C++17 | 2.2kb | 2022-03-07 23:09:41 | 2022-05-08 03:54:41 |
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,mi;}tr[N<<3];
void pushr(int x,int w){
tr[x].w+=w; tr[x].f+=w; tr[x].mi+=w;
}
void down(int k){
if(tr[k].f){pushr(k<<1,tr[k].f); pushr(k<<1|1,tr[k].f); tr[k].f=0;}
}
double F(int k){
if(k<1 || k>sz)return 2e18;
// cerr<<"F "<<k<<" : "<<stk[k]<<" "<<tr[id[k]].w<<endl;
return stk[k]*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){
if(ql<=l && qr>=r)return pushr(k,ad);
down(k); int mid=(l+r)>>1;
if(ql<=mid)change(k<<1,l,mid,ql,qr,ad);
if(qr>mid)change(k<<1|1,mid+1,r,ql,qr,ad);
tr[k].w=max(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);
}
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()
{
#define int long long
n=read(); int sumb=0,top=0;
for(int i=1;i<=n;i++){
a[i]=read(),b[i]=read();
loc[i]=1.0*(-b[i])/(1.0*a[i]);
stk[++top]=loc[i]-(1e-9),stk[++top]=loc[i],stk[++top]=loc[i]+(1e-9);
}
sort(stk+1,stk+top+1);
sz=unique(stk+1,stk+top+1)-(stk+1);
// 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]);
change(1,1,sz,loc[i]+1,sz,a[i]);
// cerr<<"change "<<loc[i]<<endl;
int res=query(1,1,sz);
// printf("%0.20lf%0.20lf\n",stk[res],stk[res+1]);
// cerr<<res<<" "<<stk[res]<<" "<<stk[res+1]<<endl;
printf("%0.8lf\n",min(F(res-1),min(F(res),F(res+1)))+sumb);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 14220kb
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.00006124 29182.68963272 152.33575652 -43566.59447730 -152219.16711349 -91537.07220745 -67289.36548581 17226.53162669 120997.16666855 140187.99342499 33494.89035968 25524.21808713 -29771.30266370 6939.06840992 -6652.85672435 -2365222.93939557 368.44273857 -115842.47724190 -33270.72039277 -76971.435...
result:
wrong answer 1st numbers differ - expected: '0.0000000', found: '0.0000612', error = '0.0000612'