QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#607938 | #5433. Absolute Difference | Luuu | WA | 2ms | 4268kb | C++20 | 5.7kb | 2024-10-03 17:11:20 | 2024-10-03 17:11:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
using db = long double;
#define fi first
#define se second
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(20);
int n, m;
cin >> n >> m;
vector<pair<int, int>> a(n), b(m);
for (auto &[l, r] : a) {
cin >> l >> r;
}
for (auto &[l, r] : b) {
cin >> l >> r;
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
auto check = [&](const vector<pair<int, int>> &t) {
for (auto [x, y] : t) {
if (x != y) {
return true;
}
}
return false;
};
auto work = [&](const vector<pair<int, int>> &t) {
vector<pair<int, int>> ret;
for (auto [x, y] : t) {
if (x != y) {
ret.push_back({x, y});
}
}
return ret;
};
bool oka = check(a), okb = check(b);
if (oka) {
a = work(a);
n = a.size();
}
if (okb) {
b = work(b);
m = b.size();
}
if (!oka && !okb) {
vector<int> s(m + 1);
for (int i = 1; i <= m; i++) {
s[i] = s[i - 1] + b[i - 1].fi;
}
auto query = [&](int ql, int qr) {
return s[qr] - s[ql - 1];
};
db ans = 0;
for (auto [x, y] : a) {
int l = -1, r = m;
while (l + 1 != r) {
int mid = (l + r) / 2;
if (b[mid].fi <= x) {
l = mid;
} else {
r = mid;
}
}
if (l == -1) {
continue;
}
ans += (l + 1) * x - query(1, l + 1);
}
for (auto [x, y] : a) {
int l = -1, r = m;
while (l + 1 != r) {
int mid = (l + r) / 2;
if (b[mid].fi >= x) {
r = mid;
} else {
l = mid;
}
}
if (r == m) {
continue;
}
ans += query(r + 1, m) - (m - r) * x;
}
ans /= n, ans /= m;
cout << ans << "\n";
return 0;
}
if (oka && !okb) {
swap(oka, okb);
swap(a, b);
}
if (!oka && okb) {
set<int> s;
for (auto [x, y] : a) {
s.insert(x);
}
for (auto [x, y] : b) {
s.insert(x);
s.insert(y);
}
vector<int> p(s.begin(), s.end());
vector<pair<int, int>> nb;
db L = 0;
for (int i = 1; i < p.size(); i++) {
int x = p[i - 1], y = p[i];
int l = -1, r = m;
while (l + 1 != r) {
int mid = (l + r) / 2;
if (b[mid].fi <= x) {
l = mid;
} else {
r = mid;
}
}
if (l == -1 || b[l].se < y) {
continue;
}
nb.push_back({x, y});
L += (y - x);
}
b = nb;
m = b.size();
vector<db> s1(m + 1), s2(m + 1);
for (int i = 1; i <= m; i++) {
s1[i] = s1[i - 1] + (b[i - 1].se - b[i - 1].fi);
s2[i] = s2[i - 1] + 1.0 * (b[i - 1].se - b[i - 1].fi) * (b[i - 1].fi + b[i - 1].se) / 2;
}
auto qry1 = [&](int ql, int qr) {
return s1[qr] - s1[ql - 1];
};
auto qry2 = [&](int ql, int qr) {
return s2[qr] - s2[ql - 1];
};
db ans = 0;
for (auto [x, y] : a) {
int l = -1, r = m;
while (l + 1 != r) {
int mid = (l + r) / 2;
if (b[mid].se <= x) {
l = mid;
} else {
r = mid;
}
}
if (l == -1) {
continue;
}
ans += x * qry1(1, l + 1) - qry2(1, l + 1);
}
for (auto [x, y] : a) {
int l = -1, r = m;
while (l + 1 != r) {
int mid = (l + r) / 2;
if (b[mid].fi >= x) {
r = mid;
} else {
l = mid;
}
}
if (r == m) {
continue;
}
ans += qry2(r + 1, m) - x * qry1(r + 1, m);
}
ans /= n;
ans /= L;
cout << ans << "\n";
return 0;
}
set<int> s;
for (auto [x, y] : a) {
s.insert(x);
s.insert(y);
}
for (auto [x, y] : b) {
s.insert(x);
s.insert(y);
}
vector<int> p(s.begin(), s.end());
vector<pair<int, int>> na;
vector<pair<int, int>> nb;
db La = 0, Lb = 0;
for (int i = 1; i < p.size(); i++) {
int x = p[i - 1], y = p[i];
int l = -1, r = m;
while (l + 1 != r) {
int mid = (l + r) / 2;
if (a[mid].fi <= x) {
l = mid;
} else {
r = mid;
}
}
if (l == -1 || a[l].se < y) {
continue;
}
na.push_back({x, y});
La += (y - x);
}
for (int i = 1; i < p.size(); i++) {
int x = p[i - 1], y = p[i];
int l = -1, r = m;
while (l + 1 != r) {
int mid = (l + r) / 2;
if (b[mid].fi <= x) {
l = mid;
} else {
r = mid;
}
}
if (l == -1 || b[l].se < y) {
continue;
}
nb.push_back({x, y});
Lb += (y - x);
}
a = na;
n = a.size();
b = nb;
m = b.size();
set<pair<int, int>> sb;
for (auto [x, y] : b) {
sb.insert({x, y});
}
vector<db> s1(m + 1), s2(m + 1);
for (int i = 1; i <= m; i++) {
s1[i] = s1[i - 1] + (b[i - 1].se - b[i - 1].fi);
s2[i] = s2[i - 1] + 1.0 * (b[i - 1].se - b[i - 1].fi) * (b[i - 1].fi + b[i - 1].se) / 2;
}
auto qry1 = [&](int ql, int qr) {
return s1[qr] - s1[ql - 1];
};
auto qry2 = [&](int ql, int qr) {
return s2[qr] - s2[ql - 1];
};
db ans = 0;
for (auto [x, y] : a) {
if (sb.count({x, y})) {
ans += 1.0 * (y - x) * (y - x) * (y - x) / 3 / La / Lb;
}
}
for (auto [x, y] : a) {
int l = -1, r = m;
while (l + 1 != r) {
int mid = (l + r) / 2;
if (b[mid].se <= x) {
l = mid;
} else {
r = mid;
}
}
// if (l == -1) {
// continue;
// }
ans += (y - x) * (0.5 * (x + y) * qry1(1, l + 1) - qry2(1, l + 1)) / La / Lb;
}
for (auto [x, y] : a) {
int l = -1, r = m;
while (l + 1 != r) {
int mid = (l + r) / 2;
if (b[mid].fi >= y) {
r = mid;
} else {
l = mid;
}
}
// if (r == m) {
// continue;
// }
ans += (y - x) * (qry2(r + 1, m) - 0.5 * (x + y) * qry1(r + 1, m)) / La / Lb;
}
cout << ans << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3932kb
input:
1 1 0 1 0 1
output:
0.33333333333333331483
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
1 1 0 1 1 1
output:
0.50000000000000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 4076kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.66666662966599687934
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
1 1 -1000000000 0 0 1000000000
output:
1000000000.00000000000000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3896kb
input:
1 1 -1000000000 -1000000000 -1000000000 1000000000
output:
1000000000.00000000000000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
1 1 -999999999 1000000000 -1000000000 -1000000000
output:
1000000000.50000000000000000000
result:
ok found '1000000000.500000000', expected '1000000000.500000000', error '0.000000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
1 1 -1000000000 1000000000 -999999999 -999999999
output:
999999999.00000000052386894822
result:
ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
1 1 1000000000 1000000000 -1000000000 -1000000000
output:
2000000000.00000000000000000000
result:
ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'
Test #9:
score: -100
Wrong Answer
time: 2ms
memory: 4268kb
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:
6708.10713162254419872355
result:
wrong answer 1st numbers differ - expected: '6717.1171457', found: '6708.1071316', error = '0.0013414'