QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21676#2822. 不等式lindongli2004#WA 3ms14220kbC++172.2kb2022-03-07 23:09:412022-05-08 03:54: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 03:54:41]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:14220kb
  • [2022-03-07 23:09:41]
  • 提交

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'