QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#21677 | #2822. 不等式 | lindongli2004# | WA | 2ms | 13920kb | C++17 | 2.3kb | 2022-03-07 23:18:39 | 2022-05-08 03:54:43 |
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,_f,mi;}tr[N<<3];
void pushr(int x,int w,int _w){
tr[x].w+=_w; tr[x].f+=w; tr[x]._f+=_w; tr[x].mi+=w;
}
void down(int k){
if(tr[k].f || tr[k]._f){pushr(k<<1,tr[k].f,tr[k]._f); pushr(k<<1|1,tr[k].f,tr[k]._f); 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]].mi+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,int ab){
if(ql<=l && qr>=r)return pushr(k,ad,ab);
down(k); int mid=(l+r)>>1;
if(ql<=mid)change(k<<1,l,mid,ql,qr,ad,ab);
if(qr>mid)change(k<<1|1,mid+1,r,ql,qr,ad,ab);
// tr[k].w=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-19),stk[++top]=loc[i],stk[++top]=loc[i]+(1e-19);
}
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],-b[i]);
change(1,1,sz,loc[i]+1,sz,a[i],b[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))));
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 13920kb
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.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 -2365222.93939394 0.00000000 -64762.47724190 0.00000000 0.00000000 -2217.27842283 0.00000000 21965.73880888 -110507.99304627 -65107.225...
result:
wrong answer 2nd numbers differ - expected: '21040.3674840', found: '0.0000000', error = '1.0000000'