QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#683091 | #5433. Absolute Difference | jielosc | WA | 2ms | 6484kb | C++20 | 3.7kb | 2024-10-27 18:43:49 | 2024-10-27 18:43:49 |
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);
}
// cout << f2(ry) << " " << f2(ly) << endl;
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 + (int)2E9) * (b[i].r - b[i].l);
suf[i].down = suf[i + 1].down + (b[i].r - b[i].l) * 2;
}
}
// cout << suf[1].up << ' ' << suf[1].down << endl;
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) {
// cout << sum << endl;
sum += calc(a[i].l, a[i].r, b[j].l, b[j].r) / (double)(a[i].r - a[i].l) / (double)(b[j].r - b[j].l);
// cout << sum << endl;
++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
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 6348kb
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: 2ms
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: 0ms
memory: 6284kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.666666626930
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 6484kb
input:
1 1 -1000000000 0 0 1000000000
output:
1000000000.000000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 6372kb
input:
1 1 -1000000000 -1000000000 -1000000000 1000000000
output:
1000000000.000000000000
result:
ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 6364kb
input:
1 1 -999999999 1000000000 -1000000000 -1000000000
output:
1000000000.500000000000
result:
ok found '1000000000.500000000', expected '1000000000.500000000', error '0.000000000'
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 6332kb
input:
1 1 -1000000000 1000000000 -999999999 -999999999
output:
-nan
result:
wrong output format Expected double, but "-nan" found