QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#396606 | #5433. Absolute Difference | Baiyu0123 | WA | 0ms | 4108kb | C++14 | 2.6kb | 2024-04-22 22:03:28 | 2024-04-22 22:03:30 |
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+=((ll)r*r-(ll)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+=((ll)r*r-(ll)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=((ll)b[i+1]*b[i+1]-(ll)b[i]*b[i])*3;
if (a[i]==3) {
E+=(ll)2*len*len*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+=(ll)C2*b[i];
E+=(ll)C1*b[i];
C1++;
C2++;
E-=(ll)(m-C2)*b[i];
E-=(ll)(n-C1)*b[i];
}
if (a[i]==1) {
E+=(ll)C2*b[i];
C1++;
E-=(ll)(m-C2)*b[i];
}
if (a[i]==2) {
E+=(ll)C1*b[i];
C2++;
E-=(ll)(n-C1)*b[i];
}
}
printf("%.12LF\n",(long double)E/n/m);
} else {
if (!(SL1==0&&SL2!=0)) {
swap(SL1,SL2);
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+=2*(ll)L2*b[i]-I2;
E+=(SI2-I2)-(ll)(SL2-L2)*b[i]*2;
}
if (a[i]&2) {
L2+=b[i+1]-b[i];
I2+=((ll)b[i+1]*b[i+1]-(ll)b[i]*b[i]);
}
}
printf("%.12LF\n",(long double)E/n/SL2/2);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3904kb
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: 3840kb
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: 3816kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.666666666686
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
1 1 -1000000000 0 0 1000000000
output:
1000000000.000000000058
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
1 1 -1000000000 -1000000000 -1000000000 1000000000
output:
1000000000.000000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
1 1 -999999999 1000000000 -1000000000 -1000000000
output:
1000000000.500000000000
result:
ok found '1000000000.500000000', expected '1000000000.500000000', error '0.000000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4108kb
input:
1 1 -1000000000 1000000000 -999999999 -999999999
output:
999999999.000000000524
result:
ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
1 1 1000000000 1000000000 -1000000000 -1000000000
output:
2000000000.000000000000
result:
ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 3960kb
input:
1000 1000 -2175 -2174 -1068 -1065 -1721 -1718 777 834 1162 1169 -3529 -3524 3966 3993 1934 1952 -234 -223 -4967 -4947 8500 8510 5272 5276 -6048 -6033 -34 -22 700 705 -7890 -7886 5538 5543 4114 4126 -9201 -9162 -1521 -1519 -5103 -5100 439 441 993 997 -1684 -1680 -8413 -8404 6724 6728 -3242 -3239 2616...
output:
3418.117307022436
result:
wrong answer 1st numbers differ - expected: '6717.1171457', found: '3418.1173070', error = '0.4911333'