QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#95844 | #5433. Absolute Difference | OWO# | WA | 2ms | 3712kb | C++20 | 5.2kb | 2023-04-12 03:23:38 | 2023-04-12 03:23:41 |
Judging History
answer
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) (x).size())
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vp = vector <pii>;
using vpl = vector <pll>;
using vl = vector<ll>;
const int inf = INT_MAX;
const ll linf = LLONG_MAX;
using db = long double;
void erase_singles(int &n, vpl &a) {
vpl a_;
for(auto &[l, r] : a)
if(l != r) a_.pb({l, r});
n = sz(a);
}
db sq(db x) {
return x * x;
}
db cb(db x) {
return x * x * x;
}
db mid(ll l, ll r) {
if(r == l) return 0;
return (db(l + r)) / 2.0;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
vpl a(n), b(m);
ll la = 0, lb = 0;
bool fa = true, fb = true;
for(auto &[l, r] : a) {
scanf("%lld %lld", &l, &r);
fa = fa && l == r;
la += r - l;
}
for(auto &[l, r] : b) {
scanf("%lld %lld", &l, &r);
fb = fb && l == r;
lb += r - l;
}
sort(all(a));
sort(all(b));
db ans = 0.0;
if(fa && fb) {
//discretas
vpl stuff;
for(int i = 0; i < n; i++) {
stuff.pb({a[i].f, 0});
}
for(int i = 0; i < m; i++) {
stuff.pb({b[i].f, 1});
}
sort(all(stuff));
array <ll, 2> sum{0, 0};
array <ll, 2> cnt{0, 0};
for(int i = 0; i < n + m; i++) {
ans += cnt[stuff[i].s ^ 1] * stuff[i].f - sum[stuff[i].s ^ 1];
cnt[stuff[i].s]++;
sum[stuff[i].s] += stuff[i].f;
}
ans /= db(n);
ans /= db(m);
}
else if(!fa && !fb) {
//continuas
erase_singles(n, a);
erase_singles(m, b);
vl b_r, b_l;
for(auto [l, r] : b) b_r.pb(r), b_l.pb(l);
vector <db> pref(m), suf(m);
for(int i = 0; i < m; i++) {
pref[i] = suf[i] = mid(b[i].s, b[i].f);
if(i) pref[i] += pref[i - 1];
}
for(int j = m - 2; j >= 0; j--) {
suf[j] += suf[j + 1];
}
for(auto [l, r] : a) {
int i = lower_bound(all(b_r), l) - begin(b_r); //primera r2 >= l1
int j = (upper_bound(all(b_l), r) - begin(b_l)) - 1; //ultima l2 <= r1
for(int k = max(0, i); k <= min(m - 1, j); k++) {
auto [x, y] = b[k];
if(y < l || x > r) continue; //no deberia pasar
if(x >= l && y <= r) {
ans += (cb(y) - cb(x)) / 3.0;
ans += mid(y, r) - mid(l, x);
}
else if(x <= l && y >= r) {
ans += (cb(r) - cb(l)) / 3.0;
ans += mid(r, y) - mid(x, l);
}
else if(y >= l) {
ans += (cb(y) - cb(l)) / 3.0;
ans += mid(y, r) - mid(x, y);
ans += mid(l, y) - mid(x, l);
}
else if(x <= r) {
ans += (cb(r) - cb(x)) / 3.0;
ans += mid(r, y) - mid(l, r);
ans += mid(x, r) - mid(l, x);
}
}
//todo antes de i son los menores
if(i - 1 >= 0) {
ans += i * mid(l, r) - pref[i - 1];
}
if(j + 1 < m) {
ans += suf[j + 1] - (m - j - 1) * mid(l, r);
}
//todo despues de j son los mayores
}
ans /= db(la);
ans /= db(lb);
}
else {
if(!fa) {
swap(n, m);
swap(a, b);
swap(la, lb);
swap(fa, fb);
}
//a es discreta, b continua
erase_singles(m, b);
vl pref(n);
vector <db> pref2(n);
vl aa;
for(int i = 0; i < n; i++) {
pref[i] = a[i].f;
pref2[i] = sq(a[i].f);
if(i) pref2[i] += pref[i - 1], pref2[i] += pref2[i - 1];
aa.pb(a[i].f);
}
for(auto [l, r] : b) {
int i = lower_bound(all(aa), l) - begin(aa);
int j = upper_bound(all(aa), r) - begin(aa);
j--;
//interseccion con puntos es exactamente [l, r]
if(i <= j) {
ll sum = pref[j];
db sq_sum = pref2[i];
if(i) sum -= pref[i - 1], sq_sum -= pref2[i - 1];
ans += db(j - i + 1) * (sq(l) + sq(r)) / 2.0 - db(sum) * (l + r) + sq_sum;
}
i--;
if(i >= 0) {
//menores son [0, i]
ll sum = pref[i];
ans += db(i + 1) * (sq(r) - sq(l)) / 2.0 - sum * db(r - l);
}
j++;
if(j < m) {//mayores son [j, m - 1]
ll sum = pref.back();
if(j) sum -= pref[j - 1];
ans += db(m - j + 1) * (sq(l) - sq(r)) / 2.0 + sum * db(r - l);
}
}
ans /= db(lb);
ans /= db(n);
}
printf("%0.9Lf\n", ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3712kb
input:
1 1 0 1 0 1
output:
0.333333333
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
1 1 0 1 1 1
output:
0.500000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 3708kb
input:
1 1 -1000000000 1000000000 -1000000000 1000000000
output:
166666666.666666667
result:
wrong answer 1st numbers differ - expected: '666666666.6666666', found: '166666666.6666667', error = '0.7500000'