QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#130414 | #5433. Absolute Difference | savacska | WA | 2ms | 5908kb | C++23 | 5.3kb | 2023-07-24 06:10:58 | 2023-07-24 06:11:01 |
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 long ll;
typedef long double ld;
pair <int, int> Alice[100005], Bob[100005];
ld pref_len[100005], pref_sq[100005], suf_len[100005], suf_sq[100005], pref_cub[100005];
ld point_seg(int x, int lef, int rig)
{
if (rig <= x) return (ld) x * (rig - lef) - ((ld) rig * rig - (ld) lef * lef) / 2.0;
if (x <= lef) return ((ld) rig * rig - (ld) lef * lef) / 2.0 - (ld) x * (rig - lef);
return (ld) x * (x - lef) - ((ld) x * x - (ld) lef * lef) / 2 + ((ld) rig * rig - (ld) x * x) / 2 - (ld) x * (rig - x);
}
ld seg_seg(int l, int r, int L, int R)
{
if (R <= l) return (ld) (R - L) * ((ld) r * r - (ld) l * l) / 2.0 - (ld) (r - l) * ((ld) R * R - (ld) L * L) / 2.0;
if (L >= r) return (ld) (r - l) * ((ld) R * R - (ld) L * L) / 2.0 - (ld) (R - L) * ((ld) r * r - (ld) l * l) / 2.0;
if (l == L && r == R) return (ld) (r - l) * (r - l) * (r - l) / 3;
if (r < R) return seg_seg(l, r, L, r) + seg_seg(l, r, r, R);
if (l > L) return seg_seg(l, r, L, l) + seg_seg(l, r, l, R);
return seg_seg(L, R, l, r);
}
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;
sort(Alice + 1, Alice + n + 1);
sort(Bob + 1, Bob + m + 1);
bool segA = false, segB = false;
for (int i = 1; i <= n; i++) if (Alice[i].x != Alice[i].y) segA = true;
for (int i = 1; i <= m; i++) if (Bob[i].x != Bob[i].y) segB = true;
if (!segA && !segB)
{
ll ans = 0;
ll sumBob = 0;
for (int i = 1; i <= m; i++) sumBob += Bob[i].x;
int uk = 0;
ll sum = 0;
for (int i = 1; i <= n; i++)
{
while (uk + 1 <= m && Bob[uk + 1].x <= Alice[i].x)
{
uk++;
sum += Bob[uk].x;
}
ans += (ll) uk * Alice[i].x - sum + (sumBob - sum) - (ll) (m - uk) * Alice[i].x;
}
ans = 1.0 * ans / n / m;
cout << fixed << ans << '\n';
return 0;
}
if (segA && !segB)
{
swap(n, m);
for (int i = 1; i <= max(n, m); i++) swap(Alice[i], Bob[i]);
swap(segA, segB);
}
if (!segA)
{
ld ans = 0;
ll sumBob = 0;
for (int i = 1; i <= m; i++) sumBob += Bob[i].y - Bob[i].x;
for (int i = 1; i <= m; i++)
{
pref_len[i] = pref_len[i - 1] + (Bob[i].y - Bob[i].x);
pref_sq[i] = pref_sq[i - 1] + ((ld) Bob[i].y * Bob[i].y - (ld) Bob[i].x * Bob[i].x) / 2.0;
}
for (int i = m; i >= 1; i--)
{
suf_len[i] = suf_len[i + 1] + (Bob[i].y - Bob[i].x);
suf_sq[i] = suf_sq[i + 1] + ((ld) Bob[i].y * Bob[i].y - (ld) Bob[i].x * Bob[i].x) / 2.0;
}
int uk = 0;
for (int i = 1; i <= n; i++)
{
while (uk + 1 <= m && Bob[uk + 1].y <= Alice[i].x) uk++;
ld pref_val = pref_len[uk] * Alice[i].x - pref_sq[uk];
ld suf_val = suf_sq[uk + 2] - suf_len[uk + 2] * Alice[i].x;
ld total = pref_val + suf_val;
if (uk != m) total += point_seg(Alice[i].x, Bob[uk + 1].x, Bob[uk + 1].y);
ans += total;
}
ans = ans / sumBob / n;
cout << fixed << ans << '\n';
return 0;
}
ll sumAlice = 0, sumBob = 0;
for (int i = 1; i <= n; i++) sumAlice += Alice[i].y - Alice[i].x;
for (int i = 1; i <= m; i++) sumBob += Bob[i].y - Bob[i].x;
for (int i = 1; i <= m; i++)
{
pref_len[i] = pref_len[i - 1] + (Bob[i].y - Bob[i].x) / 2.0;
pref_sq[i] = pref_sq[i - 1] + ((ld) Bob[i].y * Bob[i].y - (ld) Bob[i].x * Bob[i].x) / 2.0;
pref_cub[i] = pref_cub[i - 1] + (ld) (Bob[i].y - Bob[i].x) * (Bob[i].y - Bob[i].x) * (Bob[i].y - Bob[i].x) / 6;
}
for (int i = m; i >= 1; i--)
{
suf_len[i] = suf_len[i + 1] + (Bob[i].y - Bob[i].x) / 2.0;
suf_sq[i] = suf_sq[i + 1] + ((ld) Bob[i].y * Bob[i].y - (ld) Bob[i].x * Bob[i].x) / 2.0;
}
int pref = 0, suf = 1;
ld ans = 0;
for (int i = 1; i <= n; i++)
{
if (Alice[i].x == Alice[i].y) continue;
while (pref + 1 <= m && Bob[pref + 1].y <= Alice[i].x) pref++;
while (suf <= m && Bob[suf].x < Alice[i].y) suf++;
ld pref_val = pref_len[pref] * ((ld) Alice[i].y * Alice[i].y - (ld) Alice[i].x * Alice[i].x) - pref_sq[pref] * (Alice[i].y - Alice[i].x);
ld suf_val = suf_sq[suf] * (Alice[i].y - Alice[i].x) - suf_len[suf] * ((ld) Alice[i].y * Alice[i].y - (ld) Alice[i].x * Alice[i].x);
ld total = pref_val + suf_val;
if (suf - pref >= 2)
{
int L = pref + 1, R = suf - 1;
total += seg_seg(Alice[i].x, Alice[i].y, Bob[L].x, Bob[L].y);
if (R != L) total += seg_seg(Alice[i].x, Alice[i].y, Bob[R].x, Bob[R].y);
if (R - L >= 2)
{
L++, R--;
ld free_sl = pref_cub[R] - pref_cub[L - 1];
ld sec_sl = pref_sq[R] - pref_sq[L - 1];
ld thi_sl = pref_len[R] - pref_len[L - 1];
ld val = 2 * free_sl - sec_sl * (Alice[i].x + Alice[i].y) + thi_sl * ((ld) Alice[i].x * Alice[i].x + (ld) Alice[i].y * Alice[i].y);
total += val;
}
}
ans += total;
}
ans = ans / sumAlice / sumBob;
cout << fixed << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5816kb
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: 1ms
memory: 5800kb
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: 5732kb
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: 1ms
memory: 5876kb
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: 5908kb
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: 5904kb
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: 5800kb
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: 5476kb
input:
1 1 1000000000 1000000000 -1000000000 -1000000000
output:
2000000000
result:
ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'
Test #9:
score: -100
Wrong Answer
time: 2ms
memory: 5876kb
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:
6628.43462282854439093782
result:
wrong answer 1st numbers differ - expected: '6717.1171457', found: '6628.4346228', error = '0.0132025'