QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#401093 | #5433. Absolute Difference | comeintocalm | WA | 0ms | 4080kb | C++20 | 4.2kb | 2024-04-27 21:46:02 | 2024-04-27 21:46:02 |
Judging History
answer
#include <bits/stdc++.h>
using db = double;
int main() {
// freopen("in", "r", stdin);
int n, m;
scanf("%d%d", &n, &m);
std::vector<std::pair<int,int>> a(n), b(m);
std::vector<std::pair<int,int>> sa, sb;
bool fa = false, fb = false;
long long suma = 0, sumb = 0;
for (auto &[x, y] : a) {
scanf("%d%d", &x, &y);
suma += y - x;
if (x != y) {
fa = true;
}
}
for (auto &[x, y] : b) {
scanf("%d%d", &x, &y);
sumb += y - x;
if (x != y) {
fb = true;
}
}
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
int l = -1;
for (auto &&[x, y]: a) {
int r = l;
while (r + 1 < m && b[r + 1].first < y) {
++r;
}
for (int i = l + 1; i <= r && l < r; ++i) {
if (b[i].second <= x) {
sa.emplace_back(b[i]);
++l;
continue;
}
if (b[i].first < x) {
sb.emplace_back(b[i].first, x);
b[i].first = x;
}
if (b[i].first > x) {
sa.emplace_back(x, b[i].first);
x = b[i].first;
}
if (b[i].second > x) {
sa.emplace_back(x, y);
sb.emplace_back(x, y);
x = y;
b[i].first = y;
} else {
sa.emplace_back(b[i]);
sb.emplace_back(b[i]);
x = b[i].second;
b[i].first = b[i].second;
++l;
}
}
if (x < y) {
sa.emplace_back(x, y);
}
}
for (int r = l + 1; r < m; ++r) {
if (b[r].first < b[r].second) {
sb.emplace_back(b[r]);
}
}
double ans = 0;
n = sa.size(), m = sb.size();
// std::cout << n << ' ' << m << '\n';
std::vector<long long> prea, pre1(n), pre2(n);
auto get = [] (int l, int r, std::vector<long long> &pre) -> long long {
if (l > r) {
return 0;
}
if (l == 0) {
return pre[r];
}
return pre[r] - pre[l - 1];
};
if (!fa && fb) {
std::swap(fa, fb);
std::swap(a, b);
}
if (!fb) {
n = a.size();
prea.assign(n, 0);
for (int i = 0; i < n; ++i) {
prea[i] = (a[i].second + a[i].first);
if (i > 0) {
prea[i] += prea[i - 1];
}
}
// puts("q");
for (auto &[l1, r1]: b) {
int p = std::lower_bound(a.begin(), a.end(), std::make_pair(l1, r1)) - a.begin();
// printf("p %d\n", p);
ans += (1ll * (p) * l1 - get(0, p - 1, prea) / 2.0);
if (p < m) {
ans += (get(p, m - 1, prea) / 2.0 - 1ll * (m - p) * l1);
}
}
} else {
for (int i = 0; i < n; ++i) {
pre1[i] = (sa[i].second - sa[i].first);
pre2[i] = 1ll * sa[i].second * sa[i].second - 1ll * sa[i].first * sa[i].first;
if (i > 0) {
pre1[i] += pre1[i - 1];
pre2[i] += pre2[i - 1];
}
}
for (auto &[l1, r1]: sb) {
int p = std::lower_bound(sa.begin(), sa.end(), std::make_pair(l1, r1)) - sa.begin();
bool flag = false;
if (p < m) {
auto &[l2, r2] = sa[p];
if (l1 == l2 && r1 == r2) {
ans += (r1 - l1) / 3.0;
++p;
flag = true;
}
}
if (p < m) {
ans += ((db)(r1 - l1) * get(p - 1, m - 1, pre2) - (db)(1ll * r1 * r1 - 1ll * l1 * l1) * get(p - 1, m - 1, pre1)) / 2.0 / suma / sumb;
}
if (flag) {
--p;
}
if (p > 0) {
ans += ((db)(1ll * r1 * r1 - 1ll * l1 * l1) * get(0, p - 1, pre1) - (db)(r1 - l1) * get(0, p - 1, pre2)) / 2.0 / suma / sumb;
}
}
}
printf("%.16lf\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3740kb
input:
1 1 0 1 0 1
output:
0.3333333333333333
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4080kb
input:
1 1 0 1 1 1
output:
0.5000000000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4068kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.6666666269302368
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
1 1 -1000000000 0 0 1000000000
output:
1000000000.0000000000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
1 1 -1000000000 -1000000000 -1000000000 1000000000
output:
1000000000.0000000000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3876kb
input:
1 1 -999999999 1000000000 -1000000000 -1000000000
output:
0.0000000000000000
result:
wrong answer 1st numbers differ - expected: '1000000000.5000000', found: '0.0000000', error = '1.0000000'