QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#74244#5433. Absolute Differencechenshi#WA 1ms3112kbC++1.6kb2023-01-31 10:31:442023-01-31 10:31:46

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-31 10:31:46]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3112kb
  • [2023-01-31 10:31:44]
  • 提交

answer

#include<cstdio>
#include<algorithm>
#include<utility>
#include<map> 
using namespace std;
const int o=4e5+10;
int n,m,a[o],cnt,la,lb;long double pre[o],suf[o],pre_[o],suf_[o],ans;pair<int,int> p1[o],p2[o];map<int,int> mp;
inline bool inc(pair<int,int>*p,int n,int l,int r){
	pair<int,int> t=*lower_bound(p+1,p+n+1,make_pair(r,0));
	return t.second<=l&&r<=t.first;
}
inline long double calc(int x,int y,int n){
	if(!y) return 1/(long double)n;
	return x/(long double)y;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		scanf("%d%d",&p1[i].second,&p1[i].first),a[++cnt]=p1[i].first,a[++cnt]=p1[i].second,la+=p1[i].first-p1[i].second;
	for(int i=1;i<=m;++i)
		scanf("%d%d",&p2[i].second,&p2[i].first),a[++cnt]=p2[i].first,a[++cnt]=p2[i].second,lb+=p2[i].first-p2[i].second;
	sort(p1+1,p1+n+1);sort(p2+1,p2+m+1);
	sort(a+1,a+cnt+1);cnt=unique(a+1,a+cnt+1)-a-1;
	for(int i=1;i<=n;++i) if(p1[i].first==p1[i].second) mp[a[++cnt]=p1[i].first]=1;
	for(int i=1;i<=m;++i) if(p2[i].first==p2[i].second) if(mp[a[++cnt]=p2[i].first]) --cnt;
	sort(a+1,a+cnt+1);
	for(int i=1;i<cnt;pre[i]+=pre[i-1],pre_[i]+=pre_[i-1],++i)
		if(inc(p2,m,a[i],a[i+1])) pre_[i]=calc(a[i+1]-a[i],lb,m),pre[i]=pre_[i]*(a[i]+a[i+1])/2;
	for(int i=cnt;--i;suf[i]+=suf[i+1],suf_[i]+=suf_[i+1])
		if(inc(p2,m,a[i],a[i+1])) suf_[i]=calc(a[i+1]-a[i],lb,m),suf[i]=suf_[i]*(a[i]+a[i+1])/2;
	for(int i=1;i<cnt;++i) if(inc(p1,n,a[i],a[i+1])){
		ans+=(pre_[i-1]*(a[i]+a[i+1])/2-pre[i-1]+suf[i+1]-suf_[i+1]*(a[i]+a[i+1])/2)*calc(a[i+1]-a[i],la,n);
		if(inc(p2,m,a[i],a[i+1])) ans+=calc(a[i+1]-a[i],la,n)*calc(a[i+1]-a[i],lb,m)*(a[i+1]-a[i])/3;
	}
	printf("%.9Lf",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
0 1
0 1

output:

0.333333333

result:

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

Test #2:

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

input:

1 1
0 1
1 1

output:

0.500000000

result:

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

Test #3:

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

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

0.000000000

result:

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