QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#21439#2822. 不等式WhybullYMeWA 4ms3828kbC++141.7kb2022-03-05 03:21:572022-05-08 03:28:15

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:28:15]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3828kb
  • [2022-03-05 03:21:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ri int
typedef long long ll;
const int maxn=1e5+10;
template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;}
template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;}
template<class T>inline void clear(T *arr,int siz,int val=0){memset(arr,val,sizeof(T)*(siz+1));}
int a[maxn],dl,n;
double b[maxn],d[maxn];
ll ex;
struct segment_tree{
	int l,r,cnt;
	double sum;
}t[maxn<<2];
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
inline void push_up(int p){
	t[p].cnt=t[ls(p)].cnt+t[rs(p)].cnt;
	t[p].sum=t[ls(p)].sum+t[rs(p)].sum;
}
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r)return;
	ri mid=l+r>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	push_up(p);
}
void modify(int p,int k,int v){
	if(t[p].l>k||k>t[p].r)return;
	if(t[p].l==t[p].r){
		t[p].cnt+=v;
		t[p].sum+=d[t[p].l]*v;
		return;
	}
	modify(ls(p),k,v);
	modify(rs(p),k,v);
	push_up(p);
}
double query(int p,int l,int r){
	if(t[p].l>r||l>t[p].r)return 0;
	if(l<=t[p].l&&t[p].r<=r)return t[p].sum;
	return query(ls(p),l,r)+query(rs(p),l,r);
}
int kth(int p,int k){
	if(t[p].l==t[p].r)return t[p].l;
	return t[ls(p)].cnt>=k?kth(ls(p),k):kth(rs(p),k-t[ls(p)].cnt);
}
int main(){
	scanf("%d",&n);
	for(ri i=1;i<=n;++i)scanf("%d",a+i);
	for(ri i=1;i<=n;++i){
		scanf("%lf",b+i);
		if(a[i])b[i]/=a[i],d[++dl]=b[i];
	}
	sort(d+1,d+dl+1);
	dl=unique(d+1,d+dl+1)-d;
	build(1,1,dl);
	for(ri i=1;i<=n;++i){
		if(a[i])modify(1,lower_bound(d+1,d+dl+1,b[i])-d,abs(a[i]));
		else ex+=b[i];
		ri mid=t[1].cnt+1>>1,j=kth(1,mid);
		double ls=query(1,1,j);
		printf("%lf\n",mid*d[j]-ls+(t[1].sum-ls)-(t[1].cnt-mid)*d[j]+ex);
	}
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 3828kb

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:

13462.000000
21258.000000
63166.000000
129139.000000
143100.560399
148831.560399
209086.000000
302613.000000
375761.000000
449994.560399
541290.000000
625844.000000
624085.780169
628468.000000
637277.980139
656302.000000
664365.000000
723330.000000
782525.000000
792904.000000
794725.000000
824825.00...

result:

wrong answer 1st numbers differ - expected: '0.0000000', found: '13462.0000000', error = '13462.0000000'