QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#74244 | #5433. Absolute Difference | chenshi# | WA | 1ms | 3112kb | C++ | 1.6kb | 2023-01-31 10:31:44 | 2023-01-31 10:31:46 |
Judging History
answer
#include<cstdio>
#include<algorithm>
#include<utility>
#include<map>
using namespace std;
const int o=4e5+10;
int n,m,a[o],cnt,la,lb;long double pre[o],suf[o],pre_[o],suf_[o],ans;pair<int,int> p1[o],p2[o];map<int,int> mp;
inline bool inc(pair<int,int>*p,int n,int l,int r){
pair<int,int> t=*lower_bound(p+1,p+n+1,make_pair(r,0));
return t.second<=l&&r<=t.first;
}
inline long double calc(int x,int y,int n){
if(!y) return 1/(long double)n;
return x/(long double)y;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d%d",&p1[i].second,&p1[i].first),a[++cnt]=p1[i].first,a[++cnt]=p1[i].second,la+=p1[i].first-p1[i].second;
for(int i=1;i<=m;++i)
scanf("%d%d",&p2[i].second,&p2[i].first),a[++cnt]=p2[i].first,a[++cnt]=p2[i].second,lb+=p2[i].first-p2[i].second;
sort(p1+1,p1+n+1);sort(p2+1,p2+m+1);
sort(a+1,a+cnt+1);cnt=unique(a+1,a+cnt+1)-a-1;
for(int i=1;i<=n;++i) if(p1[i].first==p1[i].second) mp[a[++cnt]=p1[i].first]=1;
for(int i=1;i<=m;++i) if(p2[i].first==p2[i].second) if(mp[a[++cnt]=p2[i].first]) --cnt;
sort(a+1,a+cnt+1);
for(int i=1;i<cnt;pre[i]+=pre[i-1],pre_[i]+=pre_[i-1],++i)
if(inc(p2,m,a[i],a[i+1])) pre_[i]=calc(a[i+1]-a[i],lb,m),pre[i]=pre_[i]*(a[i]+a[i+1])/2;
for(int i=cnt;--i;suf[i]+=suf[i+1],suf_[i]+=suf_[i+1])
if(inc(p2,m,a[i],a[i+1])) suf_[i]=calc(a[i+1]-a[i],lb,m),suf[i]=suf_[i]*(a[i]+a[i+1])/2;
for(int i=1;i<cnt;++i) if(inc(p1,n,a[i],a[i+1])){
ans+=(pre_[i-1]*(a[i]+a[i+1])/2-pre[i-1]+suf[i+1]-suf_[i+1]*(a[i]+a[i+1])/2)*calc(a[i+1]-a[i],la,n);
if(inc(p2,m,a[i],a[i+1])) ans+=calc(a[i+1]-a[i],la,n)*calc(a[i+1]-a[i],lb,m)*(a[i+1]-a[i])/3;
}
printf("%.9Lf",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3112kb
input:
1 1 0 1 0 1
output:
0.333333333
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3068kb
input:
1 1 0 1 1 1
output:
0.500000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3024kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
0.000000000
result:
wrong answer 1st numbers differ - expected: '666666666.6666666', found: '0.0000000', error = '1.0000000'