QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21442#2822. 不等式WhybullYMeWA 4ms9952kbC++141.9kb2022-03-05 03:37:552022-05-08 03:28:23

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:23]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:9952kb
  • [2022-03-05 03:37:55]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ri int
typedef long long ll;
const int maxn=5e5+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[k]*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 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].cnt;
	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+=abs(b[i]);
		ri mid=t[1].cnt+1>>1,j=kth(1,mid),lc=query_(1,1,j);
		double ls=query(1,1,j);
		printf("%lf\n",lc*d[j]-ls+(t[1].sum-ls)-(t[1].cnt-lc)*d[j]+ex);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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.000000
21040.367484
46739.801169
118552.387178
134885.290924
138647.756212
181413.096885
262021.972486
332218.489221
448697.736504
526654.982723
604758.267024
622459.032072
625160.865084
633787.798909
654740.719161
679518.080335
721477.046511
781941.456093
792048.922083
806557.973974
862543.537689...

result:

wrong answer 551st numbers differ - expected: '27253367.5028660', found: '27163392.6620520', error = '0.0033014'