QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#479187 | #5433. Absolute Difference | UESTC_DECAYALI# | WA | 2ms | 10100kb | C++17 | 1.6kb | 2024-07-15 15:46:57 | 2024-07-15 15:46:57 |
Judging History
answer
#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
typedef long long LL;
typedef pair <int,int> pi;
const int N=100005;
int n,m,al[N],ar[N],bl[N],br[N],rst[N*4],cnt,lena,lenb,a[N],b[N];
signed main()
{
RI i; scanf("%lld%lld",&n,&m);
for (i=1;i<=n;++i)
{
scanf("%lld%lld",&al[i],&ar[i]);
lena+=ar[i]-al[i];
rst[++cnt]=al[i]; rst[++cnt]=ar[i];
}
for (i=1;i<=m;++i)
{
scanf("%lld%lld",&bl[i],&br[i]);
lenb+=br[i]-bl[i];
rst[++cnt]=bl[i]; rst[++cnt]=br[i];
}
sort(rst+1,rst+cnt+1); cnt=unique(rst+1,rst+cnt+1)-rst-1;
for (i=1;i<=n;++i)
{
int l=lower_bound(rst+1,rst+cnt+1,al[i])-rst;
int r=lower_bound(rst+1,rst+cnt+1,ar[i])-rst;
if (l!=r) ++a[l],--a[r]; else ++a[l];
}
for (i=1;i<=m;++i)
{
int l=lower_bound(rst+1,rst+cnt+1,bl[i])-rst;
int r=lower_bound(rst+1,rst+cnt+1,br[i])-rst;
if (l!=r) ++b[l],--b[r]; else ++b[l];
}
long double ans=0,pa=0,pb=0,sa=0,sb=0;
for (i=1;i<=cnt;++i) a[i]+=a[i-1],b[i]+=b[i-1];
for (i=1;i<=cnt;++i)
{
auto PA=[&](CI len)
{
if (lena==0) return 1.0L/n;
else return 1.0L*len/lena;
};
auto PB=[&](CI len)
{
if (lenb==0) return 1.0L/m;
else return 1.0L*len/lenb;
};
int len=rst[i+1]-rst[i];
long double mid=(rst[i+1]+rst[i])/2.0L;
if (a[i]&&b[i]) ans+=1.0L/3.0L*len*len*PA(len)*PB(len);
if (a[i])
{
ans+=PA(len)*pb*(mid-sb);
sa+=mid*PA(len); pa+=PA(len);
}
if (b[i])
{
ans+=PB(len)*pa*(mid-sa);
sb+=mid*PB(len); pb+=PB(len);
}
}
return printf("%.12Lf",ans),0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7980kb
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: 1ms
memory: 6012kb
input:
1 1 0 1 1 1
output:
0.500000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 10100kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
1333333333333333333.375000000000
result:
wrong answer 1st numbers differ - expected: '666666666.6666666', found: '1333333333333333248.0000000', error = '1999999998.9999998'