QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#661378 | #5433. Absolute Difference | xingrin | WA | 1ms | 10216kb | C++14 | 3.3kb | 2024-10-20 15:58:56 | 2024-10-20 15:58:56 |
Judging History
answer
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define F first
#define S second
#define endl '\n'
#define int ll
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<double,double> pii;
//typedef pair<double,double> pdd;
const int N = 4e5+10;
int n,m;
vector<pii> work(vector<pii> a, vector<pii> b)
{
vector<pii> now;
vector<int> pos;
for(auto [l,r]:b)
{
pos.push_back(l);
pos.push_back(r);
}
int j = 0;
for(auto [l,r] : a)
{
while(j<pos.size() && pos[j] < l)
{
j++;
}
if(j<pos.size() && pos[j]>=l && pos[j]<=r)
{
while(j<pos.size() && pos[j]<=r)
{
if(l!=pos[j]) now.push_back({l,pos[j]});
l = pos[j];
j++;
}
if(l<r) now.push_back({l,r});
}
else if(l!=r) now.push_back({l,r});
}
return now;
}
double sufl[N];
double suflm[N];
double prel[N], prelm[N];
void solve()
{
cin>>n>>m;
vector<pii> a(n),b(m);
for(int i=0;i<n;i++) cin>>a[i].F>>a[i].S;
for(int i=0;i<m;i++) cin>>b[i].F>>b[i].S;
sort(a.begin(), a.end()); sort(b.begin(), b.end());
int flaga = 1;
for(auto [l,r]:a)
{
if(l!=r) flaga = 0;
}
int flagb = 1;
for(auto [l,r]:b)
{
if(l!=r) flagb = 0;
}
vector<pii> na = a;
vector<pii> nb = b;
if(flaga == 0) na = work(a,b);
if(flagb == 0) nb = work(b,a);
na.erase(unique(na.begin(), na.end()), na.end());
nb.erase(unique(nb.begin(), nb.end()), nb.end());
n = na.size();
m = nb.size();
for(int i=m-1;i>=0;i--)
{
sufl[i] = nb[i].S - nb[i].F;
sufl[i]+=flagb;
suflm[i] = sufl[i]*(nb[i].S + nb[i].F)/2 ;
if(i!=m-1)
{
sufl[i] += sufl[i+1];
suflm[i] += suflm[i+1];
}
}
// cout<<endl;
// cout<<sufl[1]<<' '<<suflm[1]<<endl;
// cout<<endl;
double ans = 0;
for(int i=0,j=0;i<n;i++)
{
while(j<m && nb[j].F < na[i].F)
{
j++;
}
if(j>=m) break;
auto [l,r] = na[i];
if(nb[j].F == na[i].F && nb[j].S == na[i].S)
{
ans += (double)(r-l+flaga)*(r-l+flagb)* ((r*r*r - l*l*l)/3.0 + r*l*l - l*r*r);
// cout<<(double)(r-l+flaga)*(r-l+flagb)* ((r*r*r - l*l*l)/3.0 + r*l*l - l*r*r)<<endl;
j++;
}
// cout<<i<<' '<<j<<endl;
if(j<m) ans+= (r-l+flaga)*(suflm[j] - sufl[j]*(r+l)/2.0);
// cout<<ans<<endl;
}
for(int i=0;i<m;i++)
{
prel[i] = nb[i].S - nb[i].F;
prel[i] += flagb;
prelm[i] = prel[i]*(nb[i].S + nb[i].F)/2 ;
if(i!=0)
{
prel[i] += prel[i-1];
prelm[i] += prelm[i-1];
}
}
// ans = 0;
// cout<<endl;
for(int i=0,j=0;i<n;i++)
{
while(j<m && nb[j].S < na[i].S)
{
j++;
}
j--;
auto [l,r] = na[i];
// cout<<i<<' '<<j<<endl;
if(j>=0) ans+= -(r-l+flaga)*(prelm[j] - prel[j]*(r+l)/2.0);
// cout<<ans<<endl;
if(j==-1) j=0;
}
double suma = 0;
double sumb = 0;
for(int i=0;i<n;i++)
{
suma += na[i].S - na[i].F + flaga;
}
for(int i=0;i<m;i++)
{
sumb += nb[i].S - nb[i].F + flagb;
}
// cout<<endl;
// for(auto [l,r]:na) cout<<l<<' '<<r<<endl;
// cout<<endl;
// cout<<endl;
// for(auto [l,r]:nb) cout<<l<<' '<<r<<endl;
// cout<<endl;
// cout<<ans<<endl;
// cout<<suma*sumb<<endl;
ans/=(suma*sumb);
cout<<fixed<<setprecision(10)<<ans;
}
signed main()
{
IOS;
int T = 1;
// cin>>T;
while(T--)
{
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10216kb
input:
1 1 0 1 0 1
output:
0.3333333333
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 10112kb
input:
1 1 0 1 1 1
output:
0.5000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 9940kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
2666666666666667068604022784.0000000000
result:
wrong answer 1st numbers differ - expected: '666666666.6666666', found: '2666666666666667068604022784.0000000', error = '4000000000000001024.0000000'