QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#396506 | #5433. Absolute Difference | Baiyu0123 | WA | 0ms | 3912kb | C++14 | 2.5kb | 2024-04-22 20:55:07 | 2024-04-22 20:55:07 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define mkp make_pair
#define pii pair<int,int>
#define ll long long
#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/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/2);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3872kb
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: 3912kb
input:
1 1 0 1 1 1
output:
0.500000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.666666666686
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3848kb
input:
1 1 -1000000000 0 0 1000000000
output:
-781984136207968938.687500000000
result:
wrong answer 1st numbers differ - expected: '1000000000.0000000', found: '-781984136207968896.0000000', error = '781984137.2079690'