QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#285046#5433. Absolute Differenceushg8877#WA 1ms8772kbC++142.5kb2023-12-16 16:20:072023-12-16 16:20:08

Judging History

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

  • [2023-12-16 16:20:08]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8772kb
  • [2023-12-16 16:20:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=1e5+5;
int n,m; 
struct line{int l,r;}a[MAXN],b[MAXN]; 
ll c[MAXN<<2],k;ll sa,sb;
bool fa[MAXN<<2],fb[MAXN<<2];
ld pre[MAXN<<2],len[MAXN<<2];
ll ta[MAXN<<2],tb[MAXN<<2];
void solve1(){
	for(int i=1;i<=n;i++) for(int j=a[i].l+1;j<=a[i].r;j++) fa[j]=true;
	for(int i=1;i<=m;i++) for(int j=b[i].l+1;j<=b[i].r;j++) fb[j]=true;
//	cout<<a[1].l<<' '<<a[1].r<<' '<<b[1].l<<' '<<b[1].r<<' '<<k<<endl;
	ld ta=0,pa=0,tb=0,pb=0,ans=0;// 当前前缀所有数的和 desu~ 
	for(int i=1;i<=k;i++){
		if(fa[i]) ans+=(pb*(c[i]+c[i-1])/2-tb)*(c[i]-c[i-1])/sa;
		if(fb[i]) ans+=(pa*(c[i]+c[i-1])/2-ta)*(c[i]-c[i-1])/sb;
		if(fa[i]&&fb[i]) ans+=1.*(c[i]-c[i-1])/3/sa/sb;
		if(fa[i]) ta+=1.*(c[i]+c[i-1])/2*(c[i]-c[i-1])/sa,pa+=1.*(c[i]-c[i-1])/sa;
		if(fb[i]) tb+=1.*(c[i]+c[i-1])/2*(c[i]-c[i-1])/sb,pb+=1.*(c[i]-c[i-1])/sb;
	} 
	cout<<setprecision(12)<<ans<<endl;
}
void solve2(){
	for(int i=1;i<=m;i++) for(int j=b[i].l+1;j<=b[i].r;j++) fb[j]=true;
	for(int i=1;i<=k;i++){
		if(fb[i]) pre[i]=pre[i-1]+1.*(c[i]+c[i-1])*(c[i]-c[i-1])/2/sb,len[i]=len[i-1]+1.*(c[i]-c[i-1])/sb;
		else pre[i]=pre[i-1],len[i]=len[i-1];
	}
//	cout<<a[1].l<<' '<<a[1].r<<' '<<b[1].l<<' '<<b[1].r<<' '<<k<<endl;
//	cout<<c[1]<<' '<<c[2]<<endl;
//	cout<<pre[1]<<' '<<pre[2]<<endl;
//	cout<<len[1]<<' '<<len[2]<<endl;
	ld ans=0;
	for(int i=1;i<=n;i++){
		ans+=(len[a[i].l]*c[a[i].l]-pre[a[i].l])+
		((pre[k]-pre[a[i].l])-(1-len[a[i].l])*c[a[i].l])/n;
	}
	cout<<setprecision(12)<<ans<<endl;
}// sa=0
void solve3(){
	for(int i=1;i<=n;i++) ta[a[i].l]++;
	for(int i=1;i<=m;i++) tb[b[i].l]++;
	ld ans=0;
	for(int i=1;i<=k;i++){
		ta[i]+=ta[i-1];
		tb[i]+=tb[i-1];
		if(i<k) ans+=1.*(ta[i]*(m-tb[i])+tb[i]*(n-ta[i]))/n/m*(c[i+1]-c[i]);
	}
	cout<<setprecision(12)<<ans<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	vector<int> vec;
	for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r,sa+=a[i].r-a[i].l,c[++k]=a[i].l,c[++k]=a[i].r;
	for(int i=1;i<=m;i++) cin>>b[i].l>>b[i].r,sb+=b[i].r-b[i].l,c[++k]=b[i].l,c[++k]=b[i].r;
	sort(c+1,c+k+1);
	k=unique(c+1,c+k+1)-c-1;
	auto lsh=[&](int x){return lower_bound(c+1,c+k+1,x)-c;};
	for(int i=1;i<=n;i++) a[i].l=lsh(a[i].l),a[i].r=lsh(a[i].r);
	for(int i=1;i<=m;i++) b[i].l=lsh(b[i].l),b[i].r=lsh(b[i].r);
	if(sa>0&&sb>0) solve1();
	else if(sa>0||sb>0){
		if(sa>0) swap(a,b),swap(n,m),swap(sa,sb);
		solve2();
	}else solve3();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

input:

1 1
0 1
1 1

output:

0.5

result:

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

Test #3:

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

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

1.66666666667e-10

result:

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