QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#591140#5433. Absolute Differencepengpeng_fudan#WA 3ms18440kbC++235.5kb2024-09-26 14:26:492024-09-26 14:26:49

Judging History

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

  • [2024-09-26 14:26:49]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:18440kb
  • [2024-09-26 14:26:49]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long 
#define int128 __int128_t

using namespace std;

const int N = 3e5 + 10;
int n, m;
int128 al[N], ar[N], bl[N], br[N];
int128 s2[N], s1[N], s0[N];
int128 ans;

int128 calc(const int128 *a, const int128 *b) {
    vector<pair<int128, int>> c;
    for (int i = 1; i <= n; ++i) {
        c.emplace_back(a[i], 0);
    }
    for (int i = 1; i <= m; ++i) {
        c.emplace_back(b[i], 1);
    }
    sort(c.begin(), c.end());
    int128 sa0 = 0, sa1 = 0, sa2 = 0, sa3 = 0, sb0 = 0, sb1 = 0, sb2 = 0, sb3 = 0;
    int128 res = 0;
    for (int i = 0; i < n + m; ++i) {
        if (c[i].second == 0) {
            sa0 += 1;
            sa1 += c[i].first;
            sa2 += c[i].first * c[i].first;
            sa3 += c[i].first * c[i].first * c[i].first;
            res += -sb3 + 3 * sb2 * c[i].first - 3 * sb1 * c[i].first * c[i].first + sb0 * c[i].first * c[i].first * c[i].first;
        }
        else {
            sb0 += 1;
            sb1 += c[i].first;
            sb2 += c[i].first * c[i].first;
            sb3 += c[i].first * c[i].first * c[i].first;
            res += -sa3 + 3 * sa2 * c[i].first - 3 * sa1 * c[i].first * c[i].first + sa0 * c[i].first * c[i].first * c[i].first;
        }
    }
    return res;
}

int128 lsh[N];

int128 calc2(vector<pair<int128, int128>> q) {
    sort(q.begin(), q.end());
    int tot = 0;
    for (int i = 0; i < q.size(); ++i) {
        if (q[i].second == -1) {
            lsh[++tot] = q[i].first;
        }
        else {
            lsh[++tot] = q[i].second;
            lsh[++tot] = q[i].first;
        }
    }
    sort(lsh + 1, lsh + tot + 1);
    for (int i = 0; i <= tot; ++i) {
        s0[i] = s1[i] = s2[i] = 0;
    }
    for (int i = 0; i < q.size(); ++i) {
        if (q[i].second == -1) {
            int j = lower_bound(lsh + 1, lsh + tot + 1, q[i].first) - lsh;
            ++s0[j];
            s1[j] += q[i].first;
            s2[j] += q[i].first * q[i].first;
        }
    }
    for (int i = 1; i <= tot; ++i) {
        s0[i] += s0[i - 1];
        s1[i] += s1[i - 1];
        s2[i] += s2[i - 1];
    }
    int128 res = 0;
    for (int i = 0; i < q.size(); ++i) {
        if (q[i].second != -1) {
            int l = q[i].first, r = q[i].second;
            int il = lower_bound(lsh + 1, lsh + tot + 1, l) - lsh;
            int ir = lower_bound(lsh + 1, lsh + tot + 1, r) - lsh;
            res += r * r * s0[il] - l * l * s0[il] - 2 * s1[il] * r + 2 * s1[il] * l;
            res += (l * l + r * r) * (s0[ir] - s0[il]) + 2 * (s2[ir] - s2[il]) - 2 * (l + r) * (s1[ir] - s1[il]);
            res += (l * l - r * r) * (s0[tot] - s0[ir]) + 2 * (r - l) * (s1[tot] - s1[ir]);
        }
    }
    return res;
}

// int128 calc3()

signed main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; ++i) {
        int l, r;
        scanf("%lld%lld", &l, &r);
        al[i] = l, ar[i] = r;
    }
    // cerr << 1 << '\n';
    // return 0;
    for (int i = 1; i <= m; ++i) {
        int l, r;
        scanf("%lld%lld", &l, &r);
        bl[i] = l, br[i] = r;
    }
    int sa = 0, sb = 0;
    for (int i = 1; i <= n; ++i) {
        sa += ar[i] - al[i];
    }
    for (int i = 1; i <= m; ++i) {
        sb += br[i] - bl[i];
    }
    if (sa && sb) {
        ans += calc(al, br);
        ans -= calc(al, bl);
        ans += calc(ar, bl);
        ans -= calc(ar, br);
        // cerr << ans << '\n';
        // cout << (int) ans << '\n';
        
        // cerr << sa << ' ' << sb << '\n';
        long double Ans = (long double) ans;
        // cerr << Ans << '\n';
        Ans /= 6.0;
        Ans /= (long double) sa;
        Ans /= (long double) sb;
        printf("%.12Lf\n", Ans);
    }
    else if (sa && !sb) {
        vector<pair<int128, int128>> q;
        for (int i = 1; i <= n; ++i) {
            q.emplace_back(al[i], ar[i]);
        }
        for (int i = 1; i <= m; ++i) {
            q.emplace_back(bl[i], -1);
        }
        ans = calc2(q);
        long double Ans = (long double) ans;
        Ans /= 2.0;
        Ans /= (long double) sa;
        printf("%.12Lf\n", Ans);
    }
    else if (!sa && sb) {
        vector<pair<int128, int128>> q;
        for (int i = 1; i <= n; ++i) {
            q.emplace_back(al[i], -1);
        }
        for (int i = 1; i <= m; ++i) {
            q.emplace_back(bl[i], br[i]);
        }
        ans = calc2(q);
        long double Ans = (long double) ans;
        Ans /= 2.0;
        Ans /= (long double) sb;
        printf("%.12Lf\n", Ans);
    }
    else if (!sa && !sb) {
        vector<pair<int128, int>> q;
        for (int i = 1; i <= n; ++i) {
            q.emplace_back(al[i], 0);
        }
        for (int i = 1; i <= m; ++i) {
            q.emplace_back(bl[i], 1);
        }
        sort(q.begin(), q.end());
        int128 sa0 = 0, sa1 = 0, sb0 = 0, sb1 = 0;
        for (int i = 0; i < n + m; ++i) {
            // cerr << (int)q[i].first << '\n';
            if (q[i].second == 0) {
                ++sa0;
                sa1 += q[i].first;
                ans += sb0 * q[i].first - sb1;
            }
            if (q[i].second == 1) {
                ++sb0;
                sb1 += q[i].first;
                ans += sa0 * q[i].first - sa1;
                // cerr << (int)sa0 << ' ' << (int)sa1 << '\n';
            }
        }
        long double Ans = (long double) ans;
        Ans /= (long double) n;
        Ans /= (long double) m;
        printf("%.12Lf\n", Ans);
    }

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 14308kb

input:

1 1
0 1
0 1

output:

0.333333333333

result:

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

Test #2:

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

input:

1 1
0 1
1 1

output:

0.500000000000

result:

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

Test #3:

score: 0
Accepted
time: 2ms
memory: 14344kb

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.666666666686

result:

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

Test #4:

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

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000.000000000058

result:

ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'

Test #5:

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

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

1000000000.000000000000

result:

ok found '1000000000.000000000', expected '1000000000.000000000', error '0.000000000'

Test #6:

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

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

1000000000.500000000000

result:

ok found '1000000000.500000000', expected '1000000000.500000000', error '0.000000000'

Test #7:

score: 0
Accepted
time: 2ms
memory: 18264kb

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

999999999.000000000524

result:

ok found '999999999.000000000', expected '999999999.000000000', error '0.000000000'

Test #8:

score: 0
Accepted
time: 1ms
memory: 12060kb

input:

1 1
1000000000 1000000000
-1000000000 -1000000000

output:

2000000000.000000000000

result:

ok found '2000000000.000000000', expected '2000000000.000000000', error '0.000000000'

Test #9:

score: 0
Accepted
time: 3ms
memory: 14272kb

input:

1000 1000
-2175 -2174
-1068 -1065
-1721 -1718
777 834
1162 1169
-3529 -3524
3966 3993
1934 1952
-234 -223
-4967 -4947
8500 8510
5272 5276
-6048 -6033
-34 -22
700 705
-7890 -7886
5538 5543
4114 4126
-9201 -9162
-1521 -1519
-5103 -5100
439 441
993 997
-1684 -1680
-8413 -8404
6724 6728
-3242 -3239
2616...

output:

6717.117145739454

result:

ok found '6717.117145739', expected '6717.117145739', error '0.000000000'

Test #10:

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

input:

1000 1000
-5010 -4999
-2128 -2113
-5798 -5765
705 713
-3956 -3938
-5308 -5307
6759 6772
-772 -770
-860 -859
2308 2323
-5500 -5500
5140 5177
-6747 -6733
7509 7511
8864 8870
-6382 -6374
1901 1904
-5763 -5760
3019 3027
2962 2963
-314 -301
-222 -203
-726 -724
-62 -58
-1203 -1195
-5216 -5215
-4298 -4292
...

output:

6682581.127471435668

result:

wrong answer 1st numbers differ - expected: '6682.5811275', found: '6682581.1274714', error = '999.0000000'