QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#396536 | #5433. Absolute Difference | Baiyu0123 | WA | 1ms | 4112kb | C++14 | 2.5kb | 2024-04-22 21:13:33 | 2024-04-22 21:13:33 |
Judging History
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+=(1ll*r*r-1ll*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+=(1ll*r*r-1ll*l*l)*3;
}
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=(1ll*b[i+1]*b[i+1]-1ll*b[i]*b[i])*3;
if (a[i]==3) {
E+=2*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+=1ll*C2*b[i];
E+=1ll*C1*b[i];
C1++;
C2++;
E-=1ll*(m-C2)*b[i];
E-=1ll*(n-C1)*b[i];
}
if (a[i]==1) {
E+=1ll*C2*b[i];
C1++;
E-=1ll*(m-C2)*b[i];
}
if (a[i]==2) {
E+=1ll*C1*b[i];
C2++;
E-=1ll*(n-C1)*b[i];
}
}
printf("%.12LF\n",(long double)E/n/m);
} else {
if (!(L1==0&&L2!=0)) {
swap(L1,L2);
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+=1ll*L2*b[i]-I2;
E+=(SI2-I2)-1ll*(SL2-L2)*b[i];
}
if (a[i]&2) {
L2+=b[i+1]-b[i];
I2+=(1ll*b[i+1]*b[i+1]-1ll*b[i]*b[i]);
}
}
printf("%.12LF\n",(long double)E/n/SL2/2);
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4112kb
input:
1 1 0 1 0 1
output:
0.333333333333
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3888kb
input:
1 1 0 1 1 1
output:
INF
result:
wrong output format Expected double, but "INF" found