QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#396607#5433. Absolute DifferenceBaiyu0123WA 1ms5996kbC++142.6kb2024-04-22 22:04:342024-04-22 22:04:38

Judging History

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

  • [2024-04-22 22:04:38]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5996kb
  • [2024-04-22 22:04:34]
  • 提交

answer

#include<bits/stdc++.h>
#define fi first
#define se second
#define mkp make_pair
#define pii pair<int,int>
#define ll __int128
#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+=((ll)r*r-(ll)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+=((ll)r*r-(ll)l*l)*3;
	}if (n!=1&&m!=1) printf("%lld %lld\n",(int)SL1,(int)SL2);
	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=((ll)b[i+1]*b[i+1]-(ll)b[i]*b[i])*3;
			if (a[i]==3) {
				E+=(ll)2*len*len*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/SL1/SL2/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+=(ll)C2*b[i];
				E+=(ll)C1*b[i];
				C1++;
				C2++;
				E-=(ll)(m-C2)*b[i];
				E-=(ll)(n-C1)*b[i];
			}
			if (a[i]==1) {
				E+=(ll)C2*b[i];
				C1++;
				E-=(ll)(m-C2)*b[i];
			}
			if (a[i]==2) {
				E+=(ll)C1*b[i];
				C2++;
				E-=(ll)(n-C1)*b[i];
			}
		}
		printf("%.12LF\n",(long double)E/n/m);
	} else {
		if (!(SL1==0&&SL2!=0)) {
			swap(SL1,SL2);
			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+=2*(ll)L2*b[i]-I2;
				E+=(SI2-I2)-(ll)(SL2-L2)*b[i]*2;
			}
			if (a[i]&2) {
				L2+=b[i+1]-b[i];
				I2+=((ll)b[i+1]*b[i+1]-(ll)b[i]*b[i]);
			}
		}
		printf("%.12LF\n",(long double)E/n/SL2/2);
	}
	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3832kb

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: 3896kb

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: 4120kb

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.666666666686

result:

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

Test #4:

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

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000.000000000058

result:

ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'

Test #5:

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

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

1000000000.000000000000

result:

ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'

Test #6:

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

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

1000000000.500000000000

result:

ok found '1000000000.500000000', expected '1000000000.500000000', error '0.000000000'

Test #7:

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

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

999999999.000000000524

result:

ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'

Test #8:

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

input:

1 1
1000000000 1000000000
-1000000000 -1000000000

output:

2000000000.000000000000

result:

ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'

Test #9:

score: -100
Wrong Answer
time: 1ms
memory: 5996kb

input:

1000 1000
-2175 -2174
-1068 -1065
-1721 -1718
777 834
1162 1169
-3529 -3524
3966 3993
1934 1952
-234 -223
-4967 -4947
8500 8510
5272 5276
-6048 -6033
-34 -22
700 705
-7890 -7886
5538 5543
4114 4126
-9201 -9162
-1521 -1519
-5103 -5100
439 441
993 997
-1684 -1680
-8413 -8404
6724 6728
-3242 -3239
2616...

output:

9517 9519
3418.117307022436

result:

wrong answer 1st numbers differ - expected: '6717.1171457', found: '9517.0000000', error = '0.4168281'