QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#642507 | #5433. Absolute Difference | yzj123 | WA | 0ms | 4088kb | C++20 | 6.1kb | 2024-10-15 14:40:34 | 2024-10-15 14:40:35 |
Judging History
answer
#include<bits/stdc++.h>
using i64 = long long;
using db = long double;
const int inf = 2e9;
void solve() {
int n, m;
std::cin >> n >> m;
std::set<std::array<int, 2> > a, b;
db total = 0.0;
int lena = 0, lenb = 0;
std::set<int> p;
for (int i = 1; i <= n; i ++) {
int u, v;
std::cin >> u >> v;
p.insert(u);
p.insert(v);
a.insert({u, v});
lena += (v - u);
}
for (int i = 1; i <= m; i ++) {
int u, v;
std::cin >> u >> v;
p.insert(u);
p.insert(v);
b.insert({u, v});
lenb += (v - u);
}
// if (len == 0), ans = some point's place HAVE
if (lena == 0 && lenb == 0) {
int k = b.size(), oo = a.size();
std::vector<db> suf(k + 2), pre(k + 1), PRE(k + 1), SUF(k + 2);
std::vector<int> B(k + 1);
int cnt = 0;
std::map<int, int> min, max;
for (auto it : b) {
B[++ cnt] = it[0];
max[it[0]] = cnt;
if (! min.count(it[0])) {
min[it[0]] = cnt;
}
}
for (int i = 1; i <= k; i ++) {
pre[i] = pre[i - 1] + B[i];
PRE[i] = PRE[i - 1] + 1;
}
for (int i = k; i >= 1; i --) {
SUF[i] = SUF[i + 1] + 1;
suf[i] = suf[i + 1] + B[i];
}
// for (int i = 1; i<= k; i ++) {
// std::cout << B[i] << ' ';
// }
// std::cout << '\n';
b.insert({inf, inf});
for (auto it : a) {
int v = it[0];
auto o = b.lower_bound({v, 0});
auto po = o;
int idl = 0, idr = k + 1;
if (o != b.begin()) {
o = prev(o);
idl = max[(*o)[0]];
}
if (po != b.end()) {
idr = min[(*po)[0]];
}
// std::cout << idl << ' ' << idr << ' ' << v << '\n';
total += (
(PRE[idl] * v - pre[idl] +
suf[idr] - SUF[idr] * v)
);
}
printf("%.10Lf", total / oo);
// std::cout << total / oo << '\n';
return ;
} else {
if (lena != 0) {
std::swap(a, b);
std::swap(lena, lenb);
}
// a point ?
std::vector<std::array<int, 2> > dela, delb;
for (auto it : b) {
if (it[0] == it[1]) delb.push_back({it[0], it[1]});
}
for (auto it : delb) {
b.erase(it);
}
// std::cout << "???\n";
// for (auto it : a) {
// std::cout << it[0] << ' ' << it[1] << '\n';
// }
if (lena == 0) {
lena = a.size();
} else {
for (auto it : a) {
if (it[0] == it[1]) dela.push_back({it[0], it[1]});
}
for (auto it : dela) {
a.erase(it);
}
}
// std::cout << "!!!\n";
// for (auto it : a) {
// std::cout << it[0] << ' ' << it[1] << '\n';
// }
for (auto v : p) { // 断点
auto it = a.lower_bound({v, 0});
if (it != a.begin()) {
it = prev(it);
if ((*it)[1] > v) {
auto op = *it;
a.erase(it);
a.insert({op[0], v});
a.insert({v, op[1]});
}
}
it = b.lower_bound({v, 0});
if (it == b.begin()) continue;
it = prev(it);
if ((*it)[1] > v) {
auto op = *it;
b.erase(it);
b.insert({op[0], v});
b.insert({v, op[1]});
}
}
// for (auto it : a) {
// std::cout << it[0] << ' ' << it[1] << '\n';
// }
// std::cout << '\n';
// for (auto it : b) {
// std::cout << it[0] << ' ' << it[1] << '\n';
// }
int k = b.size();
std::vector<std::array<db, 2> > pre(k + 1), suf(k + 2);
std::vector<db> PRE(k + 1), SUF(k + 1);
std::vector<std::array<int, 2> > B(k + 1);
std::map<int, int> rev;
int cnt = 0;
for (auto it : b) { // * 长度贡献
B[++ cnt] = it;
rev[it[0]] = cnt;
}
// for (int i = 1; i <= k; i ++) {
// std::cout << B[i][0] << ' ' << B[i][1] << '\n';
// }
for (int i = 1; i <= k; i ++) {
pre[i][0] = pre[i - 1][0] + B[i][0] * (B[i][1] - B[i][0]);
pre[i][1] = pre[i - 1][1] + B[i][1] * (B[i][1] - B[i][0]);
PRE[i] = PRE[i - 1] + (B[i][1] - B[i][0]);
}
for (int i = k; i >= 1; i --) {
suf[i][0] = suf[i + 1][0] + B[i][0] * (B[i][1] - B[i][0]);
suf[i][1] = suf[i + 1][1] + B[i][1] * (B[i][1] - B[i][0]);
SUF[i] = SUF[i + 1] + (B[i][1] - B[i][0]);
}
b.insert({inf, inf});
for (auto it : a) {
int l = it[0], r = it[1];
auto L = b.lower_bound({l, 0}), R = b.lower_bound({r, 0});
auto com = *L;
int idl = 0, idr = k + 1;
if (L != b.begin()) {
L = prev(L);
idl = rev[(*L)[0]];
}
if (R != a.end()) {
idr = rev[(*R)[0]];
}
int LEN = (lenb - ((com[0] == l && com[1] == r) ? (r - l) : 0));
if (LEN)
total += (db)(r - l == 0 ? 1 : r - l) * (
(PRE[idl] * l + PRE[idl] * r - pre[idl][0] - pre[idl][1]) / 2
+ (suf[idr][0] + suf[idr][1] - SUF[idr] * l - SUF[idr] * r) / 2
) / LEN;
total += (r - l == 0 ? 1 : (r - l)) * ((com[0] == l && com[1] == r) ? (1.0 * (r - l) / 3) : 0);
}
// std::cout << total << ' ' << lena << '\n';
total /= lena;
printf("%.10Lf", total);
// std::cout << total << '\n';
return ;
}
}
int main() {
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3736kb
input:
1 1 0 1 0 1
output:
0.3333333333
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
1 1 0 1 1 1
output:
0.5000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.6666666240
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 4088kb
input:
1 1 -1000000000 0 0 1000000000
output:
499999999.2566906880
result:
wrong answer 1st numbers differ - expected: '1000000000.0000000', found: '499999999.2566907', error = '0.5000000'