QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#270982#5433. Absolute Differenceship2077WA 1ms6736kbC++142.7kb2023-12-01 19:25:122023-12-01 19:25:12

Judging History

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

  • [2023-12-01 19:25:12]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6736kb
  • [2023-12-01 19:25:12]
  • 提交

answer

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long double ld;
constexpr int M=2e5+5;
int n,m,num,suma,sumb,f[M],g[M],lsh[M];
pair<int,int>a[M],b[M];
ld ans,len,sum,coef,pre1[M],pre2[M];
int read(){
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
	return x*f;
}
ld Calc(ld len){return (ld)len*coef*len*len/3.0;}
void subtask1(){ len=n*m;
	for (int i=1;i<=m;i++) sum+=b[i].x/len;
	for (int i=1,j=0;i<=n;i++){
		while (j<m&&b[j+1].x<=a[i].x)
			sum-=b[++j].x*2/len;
		ans+=a[i].x*(j*2-m)/len+sum;
	}
	printf("%.15Lf\n",ans);
}
void subtask2(){ coef=(ld)1/n/sumb;
	if (suma) swap(n,m),swap(a,b),swap(suma,sumb);
	for (int i=1;i<=n;i++) lsh[++num]=a[i].x;
	for (int i=1;i<=m;i++) lsh[++num]=b[i].x,lsh[++num]=b[i].y;
	sort(lsh+1,lsh+num+1);num=unique(lsh+1,lsh+num+1)-lsh-1;
	for (int i=1;i<=n;i++) f[lower_bound(lsh+1,lsh+num+1,a[i].x)-lsh]=1;
	for (int i=1;i<=m;i++)
		g[lower_bound(lsh+1,lsh+num+1,b[i].x)-lsh]++,
		g[lower_bound(lsh+1,lsh+num+1,b[i].y)-lsh]--;
	for (int i=1;i<=num;i++) g[i]+=g[i-1];
	for (int i=1;i<=num;i++)
		if (!f[i]) pre1[i]=pre1[i-1],pre2[i]=pre2[i-1];
		else pre1[i]=pre1[i-1]+lsh[i]*coef,
			 pre2[i]=pre2[i-1]+coef;
	for (int i=1;i<=num;i++)
		if (g[i])
			ans+=(lsh[i+1]*lsh[i+1]-lsh[i]*lsh[i])*(pre2[i]-pre2[num]*0.5)
			  +(-pre1[i]+(pre1[num]-pre1[i]))*(lsh[i+1]-lsh[i]);
	printf("%.15Lf\n",ans);
}
void subtask3(){ coef=(ld)1/suma/sumb;
	for (int i=1;i<=n;i++) lsh[++num]=a[i].x,lsh[++num]=a[i].y;
	for (int i=1;i<=m;i++) lsh[++num]=b[i].x,lsh[++num]=b[i].y;
	sort(lsh+1,lsh+num+1);num=unique(lsh+1,lsh+num+1)-lsh-1;
	for (int i=1;i<=n;i++)
		f[lower_bound(lsh+1,lsh+num+1,a[i].x)-lsh]++,
		f[lower_bound(lsh+1,lsh+num+1,a[i].y)-lsh]--;
	for (int i=1;i<=m;i++)
		g[lower_bound(lsh+1,lsh+num+1,b[i].x)-lsh]++,
		g[lower_bound(lsh+1,lsh+num+1,b[i].y)-lsh]--;
	for (int i=1;i<=num;i++) f[i]+=f[i-1],g[i]+=g[i-1];
	for (int i=1;i<=num;i++)
		if (!g[i]) pre1[i]=pre1[i-1],pre2[i]=pre2[i-1];
		else pre1[i]=pre1[i-1]+(ld)(lsh[i]-lsh[i+1])*(lsh[i]+lsh[i+1])*coef,
			 pre2[i]=pre2[i-1]+(ld)(lsh[i+1]-lsh[i])*coef;
	for (int i=1;i<=num;i++) if (f[i])
		ans+=(-pre1[num]+pre1[i]+pre1[i-1]+(-pre2[num]+pre2[i]+pre2[i-1])*(lsh[i]+lsh[i+1]))*(lsh[i+1]-lsh[i])*0.5;
	for (int i=1;i<=num;i++)
		if (f[i]&&g[i]) ans+=Calc(lsh[i+1]-lsh[i]);
	printf("%.15Lf\n",ans);
}
int main(){
	n=read();m=read();
	for (int i=1;i<=n;i++) a[i]={read(),read()},suma+=a[i].y-a[i].x;
	for (int i=1;i<=m;i++) b[i]={read(),read()},sumb+=b[i].y-b[i].x;
	sort(a+1,a+n+1);sort(b+1,b+m+1);
	if (!suma&&!sumb) return subtask1(),0;
	if (!suma||!sumb) return subtask2(),0;
	return subtask3(),0;
}

詳細信息

Test #1:

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

input:

1 1
0 1
0 1

output:

0.333333333333333

result:

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

Test #2:

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

input:

1 1
0 1
1 1

output:

-nan

result:

wrong output format Expected double, but "-nan" found