QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#682922 | #5433. Absolute Difference | jielosc | WA | 2ms | 6488kb | C++20 | 3.5kb | 2024-10-27 17:56:31 | 2024-10-27 17:56:32 |
Judging History
answer
#include <bits/stdc++.h>
#define int int64_t
using std::cin;
using std::cout;
const char endl = '\n';
struct interval {
double l, r;
};
auto a = std::vector<interval>((int)1.1E5);
auto b = std::vector<interval>((int)1.1E5);
struct frac {
int up, down;
};
frac pre[(int)1.1E5];
frac suf[(int)1.1E5];
// double f1(double lx, double rx, double y) {
// return ((rx * rx - lx * lx) * y - (rx - lx) * y * y) / 2;
// }
// double f2(double lx, double rx, double y) {
// return y * y * y / 3 + (lx + rx) * y * y / 2 + (lx * lx + rx * rx) * y / 2;
// }
// double f3(double lx, double rx, double y) {
// return -f1(lx, rx, y);
// }
double calc(double lx, double rx, double ly, double ry) {
auto f1 = [&](double y) -> double {
return ((rx * rx - lx * lx) * y - (rx - lx) * y * y) / 2;
};
auto f2 = [&](double y) -> double {
return y * y * y / 3 - (lx + rx) * y * y / 2 + (lx * lx + rx * rx) * y / 2;
};
auto f3 = [&](double y) -> double { return -f1(y); };
if (ly < lx) {
if (ry <= rx) return f1(lx) - f1(ly) + f2(ry) - f2(lx);
return f1(lx) - f1(ly) + f2(rx) - f2(lx) + f3(ry) - f3(rx);
}
if (ry <= rx) return f2(ry) - f2(ly);
return f2(rx) - f2(ly) + f3(ry) - f3(rx);
}
void solve() {
int n, m;
cin >> n >> m;
int len_a = 0, len_b = 0;
for (int i = 1; i <= n; ++i) {
cin >> a[i].l >> a[i].r, len_a += a[i].r - a[i].l;
// if (a[i].l == a[i].r) a[i].r += 1E-10;
}
for (int i = 1; i <= m; ++i) {
cin >> b[i].l >> b[i].r, len_b += b[i].r - b[i].l;
// if (b[i].l == b[i].r) b[i].r += 1E-10;
}
if (len_b == 0) {
std::swap(a, b);
std::swap(n, m);
std::swap(len_a, len_b);
}
// if(len_a == 0) {
// auto pre = std::vector<double>(m + 10);
// auto suf = pre;
// if(len_b == 0) {
// for(int i = 1; i <= m; ++i) pre[i] = pre[i]
// }
// }
for (int i = 1; i <= m; ++i) {
if (len_b == 0) {
pre[i].up = pre[i - 1].up + (int)1E9 - b[i].l;
pre[i].down = pre[i - 1].down + 1;
} else {
pre[i].up =
pre[i - 1].up + (int)2E9 - (b[i].l + b[i].r) * (b[i].r - b[i].l);
pre[i].down = pre[i - 1].down + (b[i].r - b[i].l) * 2;
}
}
for (int i = m; i >= 1; --i) {
if (len_b == 0) {
suf[i].up = suf[i + 1].up + b[i].l + (int)1E9;
suf[i].down = suf[i + 1].down + 1;
} else {
suf[i].up =
suf[i + 1].up + (b[i].l + b[i].r) * (b[i].r - b[i].l) + (int)2E9;
suf[i].down = suf[i + 1].down + (b[i].r - b[i].l) * 2;
}
}
double ans = 0;
for (int i = 1, j = 1; i <= n; ++i) {
double sum = 0;
double mid = (a[i].l + a[i].r) / 2.0;
while (j <= m and b[j].r <= a[i].l) ++j;
if (pre[j - 1].down)
sum += (double)pre[j - 1].up / pre[j - 1].down - (1E9 - mid);
while (j <= m and b[j].l < a[i].r) {
sum += calc(a[i].l, a[i].r, b[j].l, b[j].r);
++j;
}
if (suf[j].down) sum += (double)suf[j].up / suf[j].down - (mid + 1E9);
if (a[i].r - a[i].l) ans += sum / (a[i].r - a[i].l);
if (len_a == 0) ans += sum;
}
cout << std::fixed;
cout << std::setprecision(12);
if (len_a == 0) len_a = n;
cout << ans / len_a << endl;
}
int32_t main() {
#ifndef _DEBUG
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
#endif
int tc = 1;
// std::cin >> tc;
while (tc--) solve();
#ifdef _DEBUG
std::cout << std::endl;
std::cout << "Time used: " << clock() << "ms" << std::endl;
system("pause");
return 0;
#endif
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 6324kb
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: 1ms
memory: 6356kb
input:
1 1 0 1 1 1
output:
0.500000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 6332kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.666666626930
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 6488kb
input:
1 1 -1000000000 0 0 1000000000
output:
0.000000000000
result:
wrong answer 1st numbers differ - expected: '1000000000.0000000', found: '0.0000000', error = '1.0000000'