QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#764186 | #5433. Absolute Difference | fosov | WA | 0ms | 3988kb | C++14 | 2.7kb | 2024-11-20 05:03:42 | 2024-11-20 05:03:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lll __int128
#define INF 0x3f3f3f3f
#define LNF 0x3f3f3f3f3f3f3f3fll
#define MOD 998244353
#define pii pair<int, int>
#define ld long double
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define N 20
int main() {
#ifdef TEST
freopen("zz.in", "r+", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout << setprecision(18);
int n, m; cin >> n >> m;
vector<pii> a(n), b(m);
ll ca = 0, cb = 0;
for (int i = 0; i < n; ++ i) cin >> a[i].fi >> a[i].se, ca += a[i].se - a[i].fi;
for (int i = 0; i < m; ++ i) cin >> b[i].fi >> b[i].se, cb += b[i].se - b[i].fi;
sort(all(a)), sort(all(b));
auto pa = [&](int l, int r) {
return ca ? (ld) (r - l) / ca : (ld) 1 / n;
};
auto pb = [&](int l, int r) {
return cb ? (ld) (r - l) / cb : (ld) 1 / m;
};
auto w = [&](int l, int r) {
return l + (ld) (r - l) / 2;
};
ld sum = 0;
for (int i = 0; i < m; ++ i) sum += w(b[i].fi, b[i].se) * pb(b[i].fi, b[i].se);
ld sl = 0, sr = 0, res = 0;
for (int i = 0, l = 0, r = 0; i < n; ++ i) {
while (l < n && b[l].se < a[i].fi) sl += w(b[i].fi, b[i].se) * pb(b[i].fi, b[i].se), ++ l;
while (r < n && b[r].fi <= a[i].se) sr += w(b[i].fi, b[i].se) * pb(b[i].fi, b[i].se), ++ r;
res += w(a[i].fi, a[i].se) * pa(a[i].fi, a[i].se) * l - sl;
res += (sum - sr) - w(a[i].fi, a[i].se) * pa(a[i].fi, a[i].se) * (n-r);
queue<pii> cur;
for (int j = l; j < r; ++ j) cur.emplace(b[j]);
while (!cur.empty()) {
auto [cl, cr] = cur.front(); cur.pop();
if (cl < a[i].fi || cr > a[i].se) {
cur.emplace(cl, a[i].fi);
cur.emplace(a[i].se, cr);
cur.emplace(max(cl, a[i].fi), min(cr, a[i].se));
continue;
}
if (cl == a[i].fi && cr == a[i].se) {
int d = a[i].se - a[i].fi;
res += (ld) d * d * d / pa(a[i].fi, a[i].se) / pb(cl, cr) / 3;
continue;
}
if (cr <= a[i].fi) {
res += w(a[i].fi, a[i].se) * pa(a[i].fi, a[i].se) - w(cl, cr) * pb(cl, cr);
continue;
}
if (cl >= a[i].se) {
res += w(cl, cr) * pb(cl, cr) - w(a[i].fi, a[i].se) * pa(a[i].fi, a[i].se);
continue;
}
}
}
cout << res << '\n';
}
// [a, b][c, d]|x - y|dxdy/wawb given b < c
// = [a,b][c,d]x - [a,b][c,d]y
// = ((b-a)(c^2-d^2)/2 - (d-c)(a^2-b^2)/2)/(b-a)(d-c)
// = mid0 - mid1
// [0,1]
// [0,1]
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3812kb
input:
1 1 0 1 0 1
output:
0.333333333333333333
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
1 1 0 1 1 1
output:
0.5
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3988kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
2.66666666666666667e+27
result:
wrong answer 1st numbers differ - expected: '666666666.6666666', found: '2666666666666666518848208896.0000000', error = '4000000000000000000.0000000'