QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#661504 | #5433. Absolute Difference | xingrin | WA | 1ms | 10128kb | C++14 | 3.9kb | 2024-10-20 16:35:16 | 2024-10-20 16:35:16 |
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<__int128,__int128> pii;
//typedef pair<double,double> pdd;
// Custom input and output operators for __int128
istream& operator>>(istream& in, __int128& x) {
string s;
in >> s;
x = 0;
bool neg = false;
int i = 0;
if (s[0] == '-') {
neg = true;
i = 1;
}
for (; i < s.size(); i++) {
x = x * 10 + (s[i] - '0');
}
if (neg) x = -x;
return in;
}
ostream& operator<<(ostream& out, __int128 x) {
if (x == 0) {
out << "0";
return out;
}
if (x < 0) {
out << "-";
x = -x;
}
string s;
while (x > 0) {
s += '0' + x % 10;
x /= 10;
}
reverse(s.begin(), s.end());
out << s;
return out;
}
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;
}
long double sufl[N];
long double suflm[N];
long 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<<sufl[0]<<endl;
// cout<<endl;
// cout<<sufl[0]<<' '<<suflm[0]<<endl;
// cout<<endl;
long 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 )
{
if(nb[j].S == na[i].S) ans += ((r*r*r - l*l*l)/3.0 + (long double)r*l*l - (long double)l*r*r);
j++;
}
if(j<m) ans+= (r-l+flaga)*(suflm[j] - sufl[j]*(r+l)/2.0);
// cout<<i<<' '<<j<<endl;
// cout<<suflm[j]<<' '<<sufl[j]<<' '<<(r+l)/2<<endl;
// 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;
}
long double suma = 0;
long 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(11)<<ans;
}
signed main()
{
IOS;
int T = 1;
// cin>>T;
while(T--)
{
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 9988kb
input:
1 1 0 1 0 1
output:
0.33333333333
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 9984kb
input:
1 1 0 1 1 1
output:
0.50000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 9992kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.66666665743
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 10128kb
input:
1 1 -1000000000 0 0 1000000000
output:
1000000000.00000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 10028kb
input:
1 1 -1000000000 -1000000000 -1000000000 1000000000
output:
0.00000000000
result:
wrong answer 1st numbers differ - expected: '1000000000.0000000', found: '0.0000000', error = '1.0000000'