QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#642507#5433. Absolute Differenceyzj123WA 0ms4088kbC++206.1kb2024-10-15 14:40:342024-10-15 14:40:35

Judging History

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

  • [2024-10-15 14:40:35]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4088kb
  • [2024-10-15 14:40:34]
  • 提交

answer

#include<bits/stdc++.h>
using i64 = long long;
using db = long double;
const int inf = 2e9;
void solve() {
    int n, m;
    std::cin >> n >> m;
    std::set<std::array<int, 2> > a, b;
    db total = 0.0;
    int lena = 0, lenb = 0;
    std::set<int> p;
    for (int i = 1; i <= n; i ++) {
        int u, v;
        std::cin >> u >> v;
        p.insert(u);
        p.insert(v);
        a.insert({u, v});
        lena += (v - u);
    }
    for (int i = 1; i <= m; i ++) {
        int u, v;
        std::cin >> u >> v;
        p.insert(u);
        p.insert(v);
        b.insert({u, v});
        lenb += (v - u);
    }
    // if (len == 0), ans = some point's place HAVE

    if (lena == 0 && lenb == 0) {
        int k = b.size(), oo = a.size();
        std::vector<db> suf(k + 2), pre(k + 1), PRE(k + 1), SUF(k + 2);
        std::vector<int> B(k + 1);
        int cnt = 0;
        std::map<int, int> min, max;
        for (auto it : b) {
            B[++ cnt] = it[0];
            max[it[0]] = cnt;
            if (! min.count(it[0])) {
                min[it[0]] = cnt;
            }
        } 
        for (int i = 1; i <= k; i ++) {
            pre[i] = pre[i - 1] + B[i];
            PRE[i] = PRE[i - 1] + 1;
        }
        for (int i = k; i >= 1; i --) {
            SUF[i] = SUF[i + 1] + 1;
            suf[i] = suf[i + 1] + B[i];
        }
        // for (int i = 1; i<= k; i ++) {
        //     std::cout << B[i] << ' ';
        // }
        // std::cout << '\n';
        b.insert({inf, inf});
        for (auto it : a) {
            int v = it[0];
            auto o = b.lower_bound({v, 0});
            auto po = o;
            int idl = 0, idr = k + 1;
            if (o != b.begin()) {
                o = prev(o);
                idl = max[(*o)[0]];
            }
            if (po != b.end()) {
                idr = min[(*po)[0]];
            }
            // std::cout << idl << ' ' << idr << ' ' << v << '\n';
            total += (
                (PRE[idl] * v - pre[idl] + 
                suf[idr] - SUF[idr] * v)
            );
        }
        printf("%.10Lf", total / oo);
        // std::cout << total / oo << '\n';
        return ;
    } else {
        if (lena != 0) {
            std::swap(a, b);
            std::swap(lena, lenb);
        } 
        // a point ? 
        std::vector<std::array<int, 2> > dela, delb;
        for (auto it : b) {
            if (it[0] == it[1]) delb.push_back({it[0], it[1]});
        }
        for (auto it : delb) {
            b.erase(it);
        }
        // std::cout << "???\n";
        // for (auto it : a) {
        //     std::cout << it[0] << ' ' << it[1] << '\n';
        // }
        if (lena == 0) {
            lena = a.size();
        } else {
            for (auto it : a) {
                if (it[0] == it[1]) dela.push_back({it[0], it[1]});
            }
            for (auto it : dela) {
                a.erase(it);
            }
        }
        // std::cout << "!!!\n";
        // for (auto it : a) {
        //     std::cout << it[0] << ' ' << it[1] << '\n';
        // }
        for (auto v : p) { // 断点
            auto it = a.lower_bound({v, 0});
            if (it != a.begin()) {
                it = prev(it);
                if ((*it)[1] > v) {
                    auto op = *it;
                    a.erase(it);
                    a.insert({op[0], v});
                    a.insert({v, op[1]});
                }
            }
            it = b.lower_bound({v, 0});
            if (it == b.begin()) continue;
            it = prev(it);
            if ((*it)[1] > v) {
                auto op = *it;
                b.erase(it);
                b.insert({op[0], v});
                b.insert({v, op[1]});
            }
        }
        // for (auto it : a) {
        //     std::cout << it[0] << ' ' << it[1] << '\n';
        // }
        // std::cout << '\n';
        // for (auto it : b) {
        //     std::cout << it[0] << ' ' << it[1] << '\n';
        // }
        int k = b.size();
        std::vector<std::array<db, 2> > pre(k + 1), suf(k + 2);
        std::vector<db> PRE(k + 1), SUF(k + 1);
        std::vector<std::array<int, 2> > B(k + 1);
        std::map<int, int> rev;
        int cnt = 0;
        for (auto it : b) { // * 长度贡献
            B[++ cnt] = it;
            rev[it[0]] = cnt;
        }
        // for (int i = 1; i <= k; i ++) {
        //     std::cout << B[i][0] << ' ' << B[i][1] << '\n';
        // }
        for (int i = 1; i <= k; i ++) {
            pre[i][0] = pre[i - 1][0] + B[i][0] * (B[i][1] - B[i][0]);
            pre[i][1] = pre[i - 1][1] + B[i][1] * (B[i][1] - B[i][0]);
            PRE[i] = PRE[i - 1] + (B[i][1] - B[i][0]);
        }
        for (int i = k; i >= 1; i --) {
            suf[i][0] = suf[i + 1][0] + B[i][0] * (B[i][1] - B[i][0]);
            suf[i][1] = suf[i + 1][1] + B[i][1] * (B[i][1] - B[i][0]);
            SUF[i] = SUF[i + 1] + (B[i][1] - B[i][0]);
        }

        b.insert({inf, inf});
        for (auto it : a) {
            int l = it[0], r = it[1];
            auto L = b.lower_bound({l, 0}), R = b.lower_bound({r, 0});
            auto com = *L;
            int idl = 0, idr = k + 1;
            if (L != b.begin()) {
                L = prev(L);
                idl = rev[(*L)[0]];
            }
            if (R != a.end()) {
                idr = rev[(*R)[0]];
            }
            int LEN = (lenb - ((com[0] == l && com[1] == r) ? (r - l) : 0));

            if (LEN) 
            total += (db)(r - l == 0 ? 1 : r - l) * (
                (PRE[idl] * l + PRE[idl] * r - pre[idl][0] - pre[idl][1]) / 2
                + (suf[idr][0] + suf[idr][1] - SUF[idr] * l - SUF[idr] * r) / 2
            ) / LEN;
            total += (r - l == 0 ? 1 : (r - l)) * ((com[0] == l && com[1] == r) ? (1.0 * (r - l) / 3) : 0);
        }
        // std::cout << total << ' ' << lena << '\n';
        total /= lena;
        printf("%.10Lf", total);
        // std::cout << total << '\n';
        return ;
    }
}
int main() {
    solve();
    return 0;
}
                

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3736kb

input:

1 1
0 1
0 1

output:

0.3333333333

result:

ok found '0.333333333', expected '0.333333333', error '0.000000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

1 1
0 1
1 1

output:

0.5000000000

result:

ok found '0.500000000', expected '0.500000000', error '0.000000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.6666666240

result:

ok found '666666666.666666627', expected '666666666.666666627', error '0.000000000'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 4088kb

input:

1 1
-1000000000 0
0 1000000000

output:

499999999.2566906880

result:

wrong answer 1st numbers differ - expected: '1000000000.0000000', found: '499999999.2566907', error = '0.5000000'