QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#117581 | #5433. Absolute Difference | UrgantTeam# | WA | 2ms | 7768kb | C++23 | 4.8kb | 2023-07-01 18:41:49 | 2023-07-01 18:41:52 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
typedef long double ld;
typedef long long ll;
pair <ll, ll> alice[100005], bob[100005];
ld pref_dif[100005], pref_square[100005], suf_dif[100005], suf_square[100005];
ld opa[100005];
ld pref_dis[100005], suf_dis[100005];
ld process(ll l, ll r, ll L, ll R)
{
if (l > L) swap(l, L), swap(r, R);
if (r <= L) return (ld) (r - l) * (R - L) * (R + L - r - l) / 2;
if (r <= R)
{
ld fir = (ld) (r - L) * (L - l) * (r - l) / 2;
ld sec = (ld) (L - l) * (R - r) * (R + r - L - l) / 2;
ld third = (ld) (r - L) * (r - L) * (r - L) / 3;
ld four = (ld) (r - L) * (R - r) * (R - L) / 2;
return fir + sec + third + four;
}
else
{
ld fir = (ld) (L - l) * (R - L) * (R - l) / 2;
ld sec = (ld) (R - L) * (R - L) * (R - L) / 3;
ld third = (ld) (r - R) * (R - L) * (r - L) / 2;
return fir + sec + third;
}
}
ld process_pt_seg(ll x, ll l, ll r)
{
if (x < l) return ((ld) r * r - (ld) l * l) / 2 - (ld) x * (r - l);
if (x > r) return (ld) x * (r - l) - ((ld) r * r - (ld) l * l) / 2;
return (ld) (x - l) * (x - l) / 2 + (ld) (r - x) * (r - x) / 2;
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
cout.precision(20);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> alice[i].x >> alice[i].y;
for (int i = 1; i <= m; i++) cin >> bob[i].x >> bob[i].y;
ll len_a = 0, len_b = 0;
for (int i = 1; i <= n; i++) len_a += alice[i].y - alice[i].x;
for (int i = 1; i <= m; i++) len_b += bob[i].y - bob[i].x;
if (len_a == 0 && len_b == 0)
{
for (int i = 1; i <= m; i++) pref_dis[i] = pref_dis[i - 1] + bob[i].x;
for (int i = m; i > 0; i--) suf_dis[i] = suf_dis[i + 1] + bob[i].x;
int lef = 0;
ld ans = 0;
for (int i = 1; i <= n; i++)
{
while (lef < m && bob[lef + 1].x <= alice[i].x) lef++;
ld sum1 = pref_dis[lef], sum2 = suf_dis[lef + 1];
ans += (ld) lef * alice[i].x - sum1;
ans += sum2 - (ld) (m - lef) * alice[i].x;
}
ans = ans / n / m;
cout << fixed << ans << '\n';
return 0;
}
if (len_b == 0)
{
for (int i = 1; i <= max(n, m); i++) swap(alice[i], bob[i]);
swap(n, m);
swap(len_a, len_b);
}
for (int i = 1; i <= m; i++) pref_dif[i] = pref_dif[i - 1] + (bob[i].y - bob[i].x);
for (int i = 1; i <= m; i++) pref_square[i] = pref_square[i - 1] + (ld) bob[i].y * bob[i].y - (ld) bob[i].x * bob[i].x;
for (int i = m; i > 0; i--) suf_dif[i] = suf_dif[i + 1] + (bob[i].y - bob[i].x);
for (int i = m; i > 0; i--) suf_square[i] = suf_square[i + 1] + (ld) bob[i].y * bob[i].y - (ld) bob[i].x * bob[i].x;
for (int i = 1; i <= m; i++)
{
opa[i] = opa[i - 1];
ld s = (bob[i].y - bob[i].x);
s = s * s * s / 3;
ld t = (ld) bob[i].x * bob[i].y * (bob[i].y - bob[i].x);
opa[i] += t + s;
}
if (len_a == 0)
{
ld ans = 0;
int lef = 0, rig = 1;
for (int i = 1; i <= n; i++)
{
while (lef < m && bob[lef + 1].y <= alice[i].x) lef++;
while (rig <= m && bob[rig].x <= alice[i].x) rig++;
ld left_part = (ld) alice[i].x * pref_dif[lef] - pref_square[lef] / 2;
ld right_part = suf_square[rig] / 2 - (ld) alice[i].x * suf_dif[rig];
ans += left_part + right_part;
if (lef != rig - 1)
{
int A = lef + 1;
ans += process_pt_seg(alice[i].x, bob[A].x, bob[A].y);
}
}
ans = ans / n / len_b;
cout << fixed << ans << '\n';
return 0;
}
ld ans = 0;
int lef = 0, rig = 1;
for (int i = 1; i <= n; i++)
{
if (alice[i].x == alice[i].y) continue;
while (lef < m && bob[lef + 1].y <= alice[i].x) lef++;
while (rig <= m && bob[rig].x < alice[i].y) rig++;
ld sum_left = (ld) (alice[i].x + alice[i].y) * pref_dif[lef] - pref_square[lef];
ld left_part = (ld) (alice[i].y - alice[i].x) / 2 * sum_left;
ld sum_right = suf_square[rig] - (ld) (alice[i].x + alice[i].y) * suf_dif[rig];
ld right_part = (ld) (alice[i].y - alice[i].x) / 2 * sum_right;
ans += left_part + right_part;
if (lef == rig - 1) continue;
int L = lef + 1, R = rig - 1;
ans += process(alice[i].x, alice[i].y, bob[L].x, bob[L].y);
if (L != R) ans += process(alice[i].x, alice[i].y, bob[R].x, bob[R].y);
if (R > L + 1)
{
int mid_lef = L + 1, mid_rig = R - 1;
ld fir = opa[mid_rig] - opa[mid_lef - 1];
ld sec = (pref_square[mid_rig] - pref_square[mid_lef - 1]) / 2;
ld third = (pref_dif[mid_rig] - pref_dif[mid_lef - 1]) / 2;
ld A = (ld) alice[i].x * alice[i].x + (ld) alice[i].y * alice[i].y;
ld B = alice[i].x + alice[i].y;
ld middle_part = A * third - B * sec + fir;
ans += middle_part;
}
}
ans = ans / len_a / len_b;
cout << fixed << ans << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5696kb
input:
1 1 0 1 0 1
output:
0.33333333333333333334
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 7652kb
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: 7764kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
666666666.66666666668606922030
result:
ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 7736kb
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: 2ms
memory: 7768kb
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: 5716kb
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: 1ms
memory: 7752kb
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: 2ms
memory: 7744kb
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: 5820kb
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:
230.38872461632317342750
result:
wrong answer 1st numbers differ - expected: '6717.1171457', found: '230.3887246', error = '0.9657012'