QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#285046 | #5433. Absolute Difference | ushg8877# | WA | 1ms | 8772kb | C++14 | 2.5kb | 2023-12-16 16:20:07 | 2023-12-16 16:20:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=1e5+5;
int n,m;
struct line{int l,r;}a[MAXN],b[MAXN];
ll c[MAXN<<2],k;ll sa,sb;
bool fa[MAXN<<2],fb[MAXN<<2];
ld pre[MAXN<<2],len[MAXN<<2];
ll ta[MAXN<<2],tb[MAXN<<2];
void solve1(){
for(int i=1;i<=n;i++) for(int j=a[i].l+1;j<=a[i].r;j++) fa[j]=true;
for(int i=1;i<=m;i++) for(int j=b[i].l+1;j<=b[i].r;j++) fb[j]=true;
// cout<<a[1].l<<' '<<a[1].r<<' '<<b[1].l<<' '<<b[1].r<<' '<<k<<endl;
ld ta=0,pa=0,tb=0,pb=0,ans=0;// 当前前缀所有数的和 desu~
for(int i=1;i<=k;i++){
if(fa[i]) ans+=(pb*(c[i]+c[i-1])/2-tb)*(c[i]-c[i-1])/sa;
if(fb[i]) ans+=(pa*(c[i]+c[i-1])/2-ta)*(c[i]-c[i-1])/sb;
if(fa[i]&&fb[i]) ans+=1.*(c[i]-c[i-1])/3/sa/sb;
if(fa[i]) ta+=1.*(c[i]+c[i-1])/2*(c[i]-c[i-1])/sa,pa+=1.*(c[i]-c[i-1])/sa;
if(fb[i]) tb+=1.*(c[i]+c[i-1])/2*(c[i]-c[i-1])/sb,pb+=1.*(c[i]-c[i-1])/sb;
}
cout<<setprecision(12)<<ans<<endl;
}
void solve2(){
for(int i=1;i<=m;i++) for(int j=b[i].l+1;j<=b[i].r;j++) fb[j]=true;
for(int i=1;i<=k;i++){
if(fb[i]) pre[i]=pre[i-1]+1.*(c[i]+c[i-1])*(c[i]-c[i-1])/2/sb,len[i]=len[i-1]+1.*(c[i]-c[i-1])/sb;
else pre[i]=pre[i-1],len[i]=len[i-1];
}
// cout<<a[1].l<<' '<<a[1].r<<' '<<b[1].l<<' '<<b[1].r<<' '<<k<<endl;
// cout<<c[1]<<' '<<c[2]<<endl;
// cout<<pre[1]<<' '<<pre[2]<<endl;
// cout<<len[1]<<' '<<len[2]<<endl;
ld ans=0;
for(int i=1;i<=n;i++){
ans+=(len[a[i].l]*c[a[i].l]-pre[a[i].l])+
((pre[k]-pre[a[i].l])-(1-len[a[i].l])*c[a[i].l])/n;
}
cout<<setprecision(12)<<ans<<endl;
}// sa=0
void solve3(){
for(int i=1;i<=n;i++) ta[a[i].l]++;
for(int i=1;i<=m;i++) tb[b[i].l]++;
ld ans=0;
for(int i=1;i<=k;i++){
ta[i]+=ta[i-1];
tb[i]+=tb[i-1];
if(i<k) ans+=1.*(ta[i]*(m-tb[i])+tb[i]*(n-ta[i]))/n/m*(c[i+1]-c[i]);
}
cout<<setprecision(12)<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
vector<int> vec;
for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r,sa+=a[i].r-a[i].l,c[++k]=a[i].l,c[++k]=a[i].r;
for(int i=1;i<=m;i++) cin>>b[i].l>>b[i].r,sb+=b[i].r-b[i].l,c[++k]=b[i].l,c[++k]=b[i].r;
sort(c+1,c+k+1);
k=unique(c+1,c+k+1)-c-1;
auto lsh=[&](int x){return lower_bound(c+1,c+k+1,x)-c;};
for(int i=1;i<=n;i++) a[i].l=lsh(a[i].l),a[i].r=lsh(a[i].r);
for(int i=1;i<=m;i++) b[i].l=lsh(b[i].l),b[i].r=lsh(b[i].r);
if(sa>0&&sb>0) solve1();
else if(sa>0||sb>0){
if(sa>0) swap(a,b),swap(n,m),swap(sa,sb);
solve2();
}else solve3();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5844kb
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: 8772kb
input:
1 1 0 1 1 1
output:
0.5
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 7876kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
1.66666666667e-10
result:
wrong answer 1st numbers differ - expected: '666666666.6666666', found: '0.0000000', error = '1.0000000'