QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#396506#5433. Absolute DifferenceBaiyu0123WA 0ms3912kbC++142.5kb2024-04-22 20:55:072024-04-22 20:55:07

Judging History

你现在查看的是最新测评结果

  • [2024-04-22 20:55:07]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3912kb
  • [2024-04-22 20:55:07]
  • 提交

answer

#include<bits/stdc++.h>
#define fi first
#define se second
#define mkp make_pair
#define pii pair<int,int>
#define ll long long
#define int long long
using namespace std;
const int maxn=4e5+1000;
pii p[maxn];int pw=0;
int b[maxn];int bw=0;
int SL1,SL2,a[maxn];
ll SI1,SI2,E,I1,I2,L1,L2,C1,C2;
signed main() {
	int n,m;
	scanf("%lld%lld",&n,&m);
	for (int i=1;i<=n;i++) {
		int l,r;
		scanf("%lld%lld",&l,&r);
		p[++pw]=mkp(l,1);
		p[++pw]=mkp(r,-1);
		b[++bw]=l;b[++bw]=r;
		SL1+=r-l;
		SI1+=(1ll*r*r-1ll*l*l)*3;
	}
	for (int i=1;i<=m;i++) {
		int l,r;scanf("%lld%lld",&l,&r);
		p[++pw]=mkp(l,2);
		p[++pw]=mkp(r,-2);
		b[++bw]=l;b[++bw]=r;
		SL2+=r-l;
		SI2+=(1ll*r*r-1ll*l*l)*3;
	}
	sort(b+1,b+bw+1);
	int k=unique(b+1,b+bw+1)-b-1;
	if (SL1!=0&&SL2!=0) {
		for (int i=1;i<=pw;i++) {
			int x=p[i].fi,y=p[i].se;
			a[lower_bound(b+1,b+k+1,x)-b]+=y;
		}
		for (int i=1;i<k;i++) {
			int len=b[i+1]-b[i];
			ll F=(1ll*b[i+1]*b[i+1]-1ll*b[i]*b[i])*3;
			if (a[i]==3) {
				E+=2*len;
				E+=L2*F-len*I2;
				E+=L1*F-len*I1;
				I2+=F;I1+=F;L2+=len;L1+=len;
				E+=len*(SI2-I2)-(SL2-L2)*F;
				E+=len*(SI1-I1)-(SL1-L1)*F;
			}
			if (a[i]==1) {
				E+=L2*F-len*I2;
				I1+=F;L1+=len;
				E+=len*(SI2-I2)-(SL2-L2)*F;
			}
			if (a[i]==2) {
				E+=L1*F-len*I1;
				I2+=F;L2+=len;
				E+=len*(SI1-I1)-(SL1-L1)*F;
			}
		}
		printf("%.12LF\n",(long double)E/6);
	} else if (SL1==0&&SL2==0) {
		for (int i=1;i<=pw;i++) {
			int x=p[i].fi,y=p[i].se;
			if (y>0) a[lower_bound(b+1,b+k+1,x)-b]+=y;
		}
		for (int i=1;i<=pw;i++) {
			if (a[i]==3) {
				E+=1ll*C2*b[i];
				E+=1ll*C1*b[i];
				C1++;
				C2++;
				E-=1ll*(m-C2)*b[i];
				E-=1ll*(n-C1)*b[i];
			}
			if (a[i]==1) {
				E+=1ll*C2*b[i];
				C1++;
				E-=1ll*(m-C2)*b[i];
			}
			if (a[i]==2) {
				E+=1ll*C1*b[i];
				C2++;
				E-=1ll*(n-C1)*b[i];
			}
		}
		printf("%.12LF\n",(long double)E/n/m);
	} else {
		if (!(L1==0&&L2!=0)) {
			swap(L1,L2);
			swap(SI1,SI2);
			swap(n,m);
			for (int i=1;i<=pw;i++) {
				if (p[i].se==1) p[i].se=2;
				else if (p[i].se==2) p[i].se=1;
				else if (p[i].se==-1) p[i].se=-2;
				else if (p[i].se==-2) p[i].se=-1;
			}
		}
		for (int i=1;i<=pw;i++) {
			int x=p[i].fi,y=p[i].se;
			if (y!=-1) a[lower_bound(b+1,b+k+1,x)-b]+=y;
		}
		SI2/=3;
		for (int i=1;i<=pw;i++) {
			if (a[i]&1) {
				E+=1ll*L2*b[i]-I2;
				E+=(SI2-I2)-1ll*(SL2-L2)*b[i];
			}
			if (a[i]&2) {
				L2+=b[i+1]-b[i];
				I2+=(1ll*b[i+1]*b[i+1]-1ll*b[i]*b[i]);
			}
		}
		printf("%.12LF\n",(long double)E/n/2);
	}
	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3872kb

input:

1 1
0 1
0 1

output:

0.333333333333

result:

ok found '0.333333333', expected '0.333333333', error '0.000000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3912kb

input:

1 1
0 1
1 1

output:

0.500000000000

result:

ok found '0.500000000', expected '0.500000000', error '0.000000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.666666666686

result:

ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3848kb

input:

1 1
-1000000000 0
0 1000000000

output:

-781984136207968938.687500000000

result:

wrong answer 1st numbers differ - expected: '1000000000.0000000', found: '-781984136207968896.0000000', error = '781984137.2079690'