QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#479187#5433. Absolute DifferenceUESTC_DECAYALI#WA 2ms10100kbC++171.6kb2024-07-15 15:46:572024-07-15 15:46:57

Judging History

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

  • [2024-07-15 15:46:57]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10100kb
  • [2024-07-15 15:46:57]
  • 提交

answer

#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
typedef long long LL;
typedef pair <int,int> pi;
const int N=100005;
int n,m,al[N],ar[N],bl[N],br[N],rst[N*4],cnt,lena,lenb,a[N],b[N];
signed main()
{
	RI i; scanf("%lld%lld",&n,&m);
	for (i=1;i<=n;++i)
	{
		scanf("%lld%lld",&al[i],&ar[i]);
		lena+=ar[i]-al[i];
		rst[++cnt]=al[i]; rst[++cnt]=ar[i];
	}
	for (i=1;i<=m;++i)
	{
		scanf("%lld%lld",&bl[i],&br[i]);
		lenb+=br[i]-bl[i];
		rst[++cnt]=bl[i]; rst[++cnt]=br[i];
	}
	sort(rst+1,rst+cnt+1); cnt=unique(rst+1,rst+cnt+1)-rst-1;
	for (i=1;i<=n;++i)
	{
		int l=lower_bound(rst+1,rst+cnt+1,al[i])-rst;
		int r=lower_bound(rst+1,rst+cnt+1,ar[i])-rst;
		if (l!=r) ++a[l],--a[r]; else ++a[l];
	}
	for (i=1;i<=m;++i)
	{
		int l=lower_bound(rst+1,rst+cnt+1,bl[i])-rst;
		int r=lower_bound(rst+1,rst+cnt+1,br[i])-rst;
		if (l!=r) ++b[l],--b[r]; else ++b[l];
	}
	long double ans=0,pa=0,pb=0,sa=0,sb=0;
	for (i=1;i<=cnt;++i) a[i]+=a[i-1],b[i]+=b[i-1];
	for (i=1;i<=cnt;++i)
	{
		auto PA=[&](CI len)
		{
			if (lena==0) return 1.0L/n;
			else return 1.0L*len/lena;
		};
		auto PB=[&](CI len)
		{
			if (lenb==0) return 1.0L/m;
			else return 1.0L*len/lenb;
		};
		int len=rst[i+1]-rst[i];
		long double mid=(rst[i+1]+rst[i])/2.0L;
		if (a[i]&&b[i]) ans+=1.0L/3.0L*len*len*PA(len)*PB(len);
		if (a[i])
		{
			ans+=PA(len)*pb*(mid-sb);
			sa+=mid*PA(len); pa+=PA(len);
		}
		if (b[i])
		{
			ans+=PB(len)*pa*(mid-sa);
			sb+=mid*PB(len); pb+=PB(len);
		}
	}
	return printf("%.12Lf",ans),0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 6012kb

input:

1 1
0 1
1 1

output:

0.500000000000

result:

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

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 10100kb

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

1333333333333333333.375000000000

result:

wrong answer 1st numbers differ - expected: '666666666.6666666', found: '1333333333333333248.0000000', error = '1999999998.9999998'