QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#768241 | #5433. Absolute Difference | DAleksa | WA | 1ms | 3932kb | C++14 | 2.7kb | 2024-11-21 05:04:38 | 2024-11-21 05:04:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const long double eps = 1e-12;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(12);
int n, m;
cin >> n >> m;
vector<long double> l1(n), r1(n), l2(m), r2(m);
for(int i = 0; i < n; i++) cin >> l1[i] >> r1[i];
for(int i = 0; i < m; i++) cin >> l2[i] >> r2[i];
vector<pair<long double, pair<int, int>>> events;
for(int i = 0; i < n; i++) {
events.push_back({l1[i], {1, 0}});
events.push_back({r1[i] + eps, {-1, 0}});
events.push_back({l2[i], {1, 1}});
events.push_back({r2[i] + eps, {-1, 1}});
}
sort(events.begin(), events.end());
vector<pair<long double, long double>> a, b;
vector<int> cnt(2, 0);
cnt[events[0].second.second] += events[0].second.first;
for(int i = 1; i < events.size(); i++) {
if(events[i - 1].first < events[i].first) {
if(cnt[0] > 0) a.push_back({events[i - 1].first, events[i].first});
if(cnt[1] > 0) b.push_back({events[i - 1].first, events[i].first});
}
cnt[events[i].second.second] += events[i].second.first;
}
// for(int i = 0; i < a.size(); i++) cout << a[i].first << " " << a[i].second << "\n";
// for(int i = 0; i < b.size(); i++) cout << b[i].first << " " << b[i].second << "\n";
long double ans = 0;
{
vector<long double> sum(a.size()), prod(a.size());
sum[0] = a[0].second - a[0].first;
for(int i = 1; i < a.size(); i++) sum[i] = sum[i - 1] + a[i].second - a[i].first;
prod[0] = (a[0].second - a[0].first) * 1.0 * (a[0].first + a[0].second) / 2.0;
for(int i = 1; i < a.size(); i++) prod[i] = prod[i - 1] + (a[i].second - a[i].first) * 1.0 * (a[i].first + a[i].second) / 2.0;
for(int i = 0; i < b.size(); i++) {
int j = lower_bound(a.begin(), a.end(), b[i]) - a.begin();
if(a[j] == b[i]) ans += (a[j].second - a[j].first) * (b[i].second - b[i].first) / 3.0;
if(j > 0) {
ans += (b[i].first + b[i].second) / 2.0 * (b[i].second - b[i].first) * sum[j - 1] - (b[i].second - b[i].first) * prod[j - 1];
}
if(j < a.size() - 1) {
ans += (b[i].first + b[i].second) / 2.0 * (b[i].second - b[i].first) * (sum[a.size() - 1] - sum[j]) - (b[i].second - b[i].first) * (prod[a.size() - 1] - prod[j]);
}
}
}
long double S = 0, T = 0;
for(int i = 0; i < a.size(); i++) S += a[i].second - a[i].first;
for(int i = 0; i < b.size(); i++) T += b[i].second - b[i].first;
cout << fixed << setprecision(12) << ans / (S * T);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3932kb
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: 3824kb
input:
1 1 0 1 1 1
output:
0.500000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3828kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
0.333333333333
result:
wrong answer 1st numbers differ - expected: '666666666.6666666', found: '0.3333333', error = '1.0000000'