QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#400913 | #5433. Absolute Difference | comeintocalm | WA | 1ms | 4100kb | C++20 | 3.1kb | 2024-04-27 18:10:51 | 2024-04-27 18:10:52 |
Judging History
answer
#include <bits/stdc++.h>
int main() {
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;
for (auto &[x, y] : a) {
scanf("%d%d", &x, &y);
if (x != y) {
fa = true;
}
}
for (auto &[x, y] : b) {
scanf("%d%d", &x, &y);
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 < m && b[r + 1].first < y) {
++r;
}
for (int i = l + 1; i <= r; ++i) {
if (b[i].second <= x) {
sa.emplace_back(b[i]);
++l;
}
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;
}
}
}
long double ans = 0;
n = sa.size(), m = sb.size();
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();
auto &[l2, r2] = sa[p];
bool flag = false;
if (l1 == l2 && r1 == r2) {
ans += (r1 - l1) / 3.0;
++p;
flag = true;
}
if (p < m) {
ans += ((r1 - l1) * get(p - 1, m - 1, pre2) - (1ll * r1 * r1 - 1ll * l1 * l1) * get(p - 1, m - 1, pre1)) / 2.0;
}
if (flag) {
--p;
}
--p;
if (p >= 0) {
ans += ((r1 - l1) * get(0, p - 1, pre2) - (1ll * r1 * r1 - 1ll * l1 * l1) * get(p - 1, m - 1, pre1)) / 2.0;
}
}
}
printf("%.16Lf\n", ans);
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4100kb
input:
1 1 0 1 0 1
output:
0.1666666666666667
result:
wrong answer 1st numbers differ - expected: '0.3333333', found: '0.1666667', error = '0.1666667'