QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#95844#5433. Absolute DifferenceOWO#WA 2ms3712kbC++205.2kb2023-04-12 03:23:382023-04-12 03:23:41

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-12 03:23:41]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3712kb
  • [2023-04-12 03:23:38]
  • 提交

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'