QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#21277#2822. 不等式DaBenZhongXiaSongKuaiDi#Compile Error//C111.6kb2022-03-04 14:24:512022-05-18 04:11:12

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-18 04:11:12]
  • 评测
  • [2022-03-04 14:24:51]
  • 提交

answer

#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=5e5+10;
db a[N],b[N],Zero[N],v[N],S;
int n,z[N],len;
db tmp[N];
db sum[N<<2],s[N<<2];
#define lson (id<<1)
#define rson (id<<1|1)
#define mid ((l+r)>>1)
const db eps=1e-8;
void update(int id){
	sum[id]=sum[lson]+sum[rson];
	s[id]=s[lson]+s[rson];
}
void add(int id,int l,int r,int pos,db k1,db k2){
	if(l==r){
		sum[id]+=k1;
		s[id]+=k2;
		return;
	}
	if(pos<=mid) add(lson,l,mid,pos,k1,k2);
	else add(rson,mid+1,r,pos,k1,k2);
	update(id);
}
int Find(int id,int l,int r,db k){
	if(l==r)return l;
	if(sum[lson]>k||fabs(sum[lson]-k)<eps) return Find(lson,l,mid,k);
	else return Find(rson,mid+1,r,k-sum[lson]);
}
db query1(int id,int l,int r,int L,int R){
	if(r<L||R<l)return 0;
	if(L<=l&&r<=R)return sum[id];
	return query1(lson,l,mid,L,R)+query1(rson,mid+1,r,L,R);
}
db query2(int id,int l,int r,int L,int R){
	if(r<L||R<l)return 0;
	if(L<=l&&r<=R)return s[id];
	return query2(lson,l,mid,L,R)+query2(rson,mid+1,r,L,R);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
	for(int i=1;i<=n;i++) scanf("%lf",&b[i]);
	for(int i=1;i<=n;i++){
		v[i]=Zero[i]=-b[i]/a[i];
	}
	sort(v+1,v+1+n);
	for(int i=1;i<=n;i++){
		if(fabs(tmp[len]-v[i])>eps){
			tmp[++len]=v[i];
		}
	}
	memset(v,0.0,sizeof(v));
	for(int i=1;i<=len;i++) v[i]=tmp[i];
	for(int i=1;i<=n;i++) z[i]=lower_bound(v+1,v+1+len,Zero[i])-v;
	for(int i=1;i<=n;i++){
		add(1,1,len,z[i],a[i],b[i]);
		S+=a[i];
		int k=Find(1,1,len,S/2);
		printf("%.6lf\n",v[k]*(query1(1,1,len,1,k-1)-query1(1,1,len,k+1,len))-query2(1,1,len,k+1,len)+query2(1,1,len,1,k-1));
	}
	return 0;
}

詳細信息

answer.code:1:9: fatal error: bits/stdc++.h: No such file or directory
 #include<bits/stdc++.h>
         ^~~~~~~~~~~~~~~
compilation terminated.