QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#661528 | #5433. Absolute Difference | xingrin | WA | 2ms | 10584kb | C++14 | 3.9kb | 2024-10-20 16:40:16 | 2024-10-20 16:40:17 |
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<long double,long double> pii;
// 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)
{
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++;
// cout<<ans<<endl;
}
if(j<m) ans+= (r-l+flaga)*(suflm[j] - sufl[j]*(r+l)/2.0);
// 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: 0ms
memory: 9992kb
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: 2ms
memory: 9988kb
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: 1ms
memory: 9928kb
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: 1ms
memory: 10132kb
input:
1 1 -1000000000 0 0 1000000000
output:
1000000000.00000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 10012kb
input:
1 1 -1000000000 -1000000000 -1000000000 1000000000
output:
1000000000.00000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 10216kb
input:
1 1 -999999999 1000000000 -1000000000 -1000000000
output:
1000000000.50000000000
result:
ok found '1000000000.500000000', expected '1000000000.500000000', error '0.000000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 10004kb
input:
1 1 -1000000000 1000000000 -999999999 -999999999
output:
999999999.00000000052
result:
ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'
Test #8:
score: 0
Accepted
time: 2ms
memory: 9988kb
input:
1 1 1000000000 1000000000 -1000000000 -1000000000
output:
2000000000.00000000000
result:
ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'
Test #9:
score: 0
Accepted
time: 2ms
memory: 10584kb
input:
1000 1000 -2175 -2174 -1068 -1065 -1721 -1718 777 834 1162 1169 -3529 -3524 3966 3993 1934 1952 -234 -223 -4967 -4947 8500 8510 5272 5276 -6048 -6033 -34 -22 700 705 -7890 -7886 5538 5543 4114 4126 -9201 -9162 -1521 -1519 -5103 -5100 439 441 993 997 -1684 -1680 -8413 -8404 6724 6728 -3242 -3239 2616...
output:
6717.11714573945
result:
ok found '6717.117145739', expected '6717.117145739', error '0.000000000'
Test #10:
score: 0
Accepted
time: 2ms
memory: 10500kb
input:
1000 1000 -5010 -4999 -2128 -2113 -5798 -5765 705 713 -3956 -3938 -5308 -5307 6759 6772 -772 -770 -860 -859 2308 2323 -5500 -5500 5140 5177 -6747 -6733 7509 7511 8864 8870 -6382 -6374 1901 1904 -5763 -5760 3019 3027 2962 2963 -314 -301 -222 -203 -726 -724 -62 -58 -1203 -1195 -5216 -5215 -4298 -4292 ...
output:
6682.58112747144
result:
ok found '6682.581127471', expected '6682.581127471', error '0.000000000'
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 10348kb
input:
1000 1000 770 770 5869 5869 -8786 -8786 7549 7549 -4165 -4165 4023 4023 -9779 -9779 7797 7797 1105 1105 508 508 7653 7653 -359 -359 9393 9393 -9363 -9363 -4160 -4160 -3682 -3682 9409 9409 -8548 -8548 -9908 -9908 -7494 -7494 3751 3751 2326 2326 -3311 -3311 3651 3651 -7663 -7663 5376 5376 -7071 -7071 ...
output:
6673.75457183424
result:
wrong answer 1st numbers differ - expected: '6673.7568169', found: '6673.7545718', error = '0.0000003'