QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#761840#5433. Absolute DifferenceSGColin#WA 0ms3852kbC++144.9kb2024-11-19 10:40:162024-11-19 10:40:16

Judging History

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

  • [2024-11-19 10:40:16]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3852kb
  • [2024-11-19 10:40:16]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tii;

#define eb emplace_back
#define pb push_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

int main() {
    vector<pii> tmp, A, B;
    int n = rd(), m = rd();
    bool intervalA = false, intervalB = false;
    rep(i, 1, n) {
        int l = rd(), r = rd();
        tmp.eb(l, r);
        intervalA |= (l != r);
    }
    for (auto [l, r] : tmp) {
        if (intervalA && l == r) continue;
        A.eb(l, r);
    }
    tmp.clear();
    rep(i, 1, m) {
        int l = rd(), r = rd();
        tmp.eb(l, r);
        intervalB |= (l != r);
    }
    for (auto [l, r] : tmp) {
        if (intervalB && l == r) continue;
        B.eb(l, r);
    }
    if (!intervalA && !intervalB) {
        double ans = 0;
        sort(all(A));
        sort(all(B));
        int ptr = 0;
        double sumL = 0, sumR = 0;
        for (auto [l, r] : A) sumR += l;
        for (auto [l, r] : B) {
            while (ptr < A.size() && A[ptr].first <= l) {
                sumL += A[ptr].first;
                sumR -= A[ptr].first;
                ++ptr;
            }
            ans += l * ptr - sumL + sumR - l * (A.size() - ptr);
        }
        ans = ans / A.size() / B.size();
        printf("%.12lf\n", ans);
        return 0;
    }
    if (!intervalB) {swap(intervalA, intervalB); swap(A, B); swap(n, m);}
    if (!intervalA) {
        double ans = 0;
        sort(all(A));
        sort(all(B));
        int ptr = 0;
        double sumL = 0, sumR = 0, sumL2 = 0, sumR2 = 0;
        for (auto [l, r] : B) {
            sumR += r - l;
            sumR2 += 1.0 * r * r - 1.0 * l * l;
        }
        for (auto [l, r] : A) {
            while (ptr < B.size() && B[ptr].second <= l) {
                auto [ll, rr] = B[ptr];
                double contri = 1.0 * rr * rr - 1.0 * ll * ll;
                sumL += rr - ll;
                sumR -= rr - ll;
                sumL2 += contri;
                sumR2 -= contri;
                ++ptr;
            }
            if (ptr < B.size() && l >= B[ptr].first && l <= B[ptr].second) {
                auto [ll, rr] = B[ptr];
                double contri = 1.0 * rr * rr - 1.0 * ll * ll;
                sumR -= rr - ll;
                sumR2 -= contri;
                ans += l * sumL - sumL2 / 2;
                ans += sumR2 / 2 - l * sumR;
                ans += l * (l - ll) - (1.0 * l * l - 1.0 * ll * ll) / 2;
                ans += (1.0 * rr * rr - 1.0 * l * l) / 2 - l * (rr - l);
                sumR += rr - ll;
                sumR += contri;
            } else {
                ans += l * sumL - sumL2 / 2;
                ans += sumR2 / 2 - l * sumR;
            }
        }
        ans = ans / A.size();
        printf("%.12lf\n", ans);
        return 0;
    }
    int ptrA = 0, ptrB = 0;
    vector<int> S;
    for (auto [l, r] : A) S.eb(l), S.eb(r);
    for (auto [l, r] : B) S.eb(l), S.eb(r);
    sort(all(S));
    S.erase(unique(all(S)), S.end());
    auto cut = [&](vector<pii> &seg) {
        vector<pii> res;
        int ptr = 0;
        for (auto [l, r] : seg) {
            while (S[ptr] <= l) ++ptr;
            while (S[ptr] <= r) {
                res.eb(S[ptr - 1], S[ptr]);
                ++ptr;
            }
        }
        swap(seg, res);
    };
    cut(A); cut(B);
    int ptr = 0;
    double ans = 0, sumL = 0, sumR = 0, sumL2 = 0, sumR2 = 0;
    for (auto [l, r] : A) sumR += r - l, sumR2 += 1.0 * r * r - 1.0 * l * l;
    for (auto [l, r] : B) {
        while (ptr < A.size() && A[ptr].second <= l) {
            auto [ll, rr] = A[ptr];
            double contri = 1.0 * rr * rr - 1.0 * ll * ll;
            sumL += rr - ll;
            sumR -= rr - ll;
            sumL2 += contri;
            sumR2 -= contri;
            ++ptr;
        }
        double c1 = r - l;
        double c2 = 1.0 * r * r - 1.0 * l * l;
        if (ptr < A.size() && l == A[ptr].first && r == A[ptr].second) {
            auto [ll, rr] = A[ptr];
            double contri = 1.0 * rr * rr - 1.0 * ll * ll;
            sumR -= rr - ll;
            sumR2 -= contri;
            ans += c2 * sumL / 2 - c1 * sumL2 / 2;
            ans += c1 * sumR2 / 2 - c2 * sumR / 2;
            ans += c1 * c1 * c1 / 3;
            sumR += rr - ll;
            sumR += contri;
        } else {
            ans += c2 * sumL / 2 - c1 * sumL2 / 2;
            ans += c1 * sumR2 / 2 - c2 * sumR / 2;
        }
    }
    printf("%.12lf\n", ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3852kb

input:

1 1
0 1
0 1

output:

1.333333333333

result:

wrong answer 1st numbers differ - expected: '0.3333333', found: '1.3333333', error = '1.0000000'