QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21679#2822. 不等式lindongli2004#WA 1ms14064kbC++172.4kb2022-03-07 23:23:472022-05-08 03:54:57

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 03:54:57]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:14064kb
  • [2022-03-07 23:23:47]
  • 提交

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();
	for(int i=1;i<=n;i++)b[i]=read();
	for(int i=1;i<=n;i++)
		if(a[i]<0)a[i]=-a[i],b[i]=-b[i];
	for(int i=1;i<=n;i++){
		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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 14064kb

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
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.0...

result:

wrong answer 2nd numbers differ - expected: '21040.3674840', found: '0.0000000', error = '1.0000000'