QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#617746#5433. Absolute DifferenceCipherxzc#WA 2ms12132kbC++234.1kb2024-10-06 16:52:472024-10-06 16:52:51

Judging History

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

  • [2024-10-06 16:52:51]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12132kb
  • [2024-10-06 16:52:47]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using db = long double;

struct node{
    LL l, r;
    db x, k;
};

bool operator<(const node &a, const node &b){
    return a.l < b.l;
}

const int N = 2e5 + 5;
LL n, m, l1[N], r1[N], l2[N], r2[N];
db s[N << 1], ks[N << 1]; // s: sigma(k2 * x2), ks: sigma(k2)

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    vector<LL> used;
    db len1 = 0, len2 = 0;
    bool flag1 = true, flag2 = true;
    for (int i = 1; i <= n; i++){
        cin >> l1[i] >> r1[i];
        used.push_back(l1[i]);
        used.push_back(r1[i]);
        len1 += r1[i] - l1[i];
        if (l1[i] != r1[i]){
            flag1 = false;
        }
    }
    for (int i = 1; i <= m; i++){
        cin >> l2[i] >> r2[i];
        used.push_back(l2[i]);
        used.push_back(r2[i]);
        len2 += r2[i] - l2[i];
        if (l2[i] != r2[i]){
            flag2 = false;
        }
    }
    sort(used.begin(), used.end());
    used.erase(unique(used.begin(), used.end()), used.end());

    vector<node> vec1, vec2;
    int p = 0;
    if (flag1){
        for (int i = 1; i <= n; i++){
            assert(l1[i] == r1[i]);
            vec1.emplace_back(l1[i], r1[i], l1[i], db(1.0) / n);
        }
    }else{
        for (int i = 1; i <= n; i++){
            if (l1[i] == r1[i]){
                continue;
            }
            while (p < used.size() && used[p] < l1[i]){
                p++;
            }
            p++;
            while (p < used.size() && used[p] <= r1[i]){
                db gg = db(used[p - 1] + used[p]) / 2;
                db jj = (used[p] - used[p - 1]) / len1;
                vec1.emplace_back(used[p - 1], used[p], gg, jj);
                p++;
            }
        }
    }
    if (flag2){
        for (int i = 1; i <= m; i++){
            assert(l2[i] == r2[i]);
            vec2.emplace_back(l2[i], r2[i], l2[i], db(1.0) / m);
        }
    }else{
        p = 0;
        for (int i = 1; i <= m; i++){
            if (l2[i] == r2[i]){
                continue;
            }
            while (p < used.size() && used[p] < l2[i]){
                p++;
            }
            p++;
            while (p < used.size() && used[p] <= r2[i]){
                db gg = db(used[p - 1] + used[p]) / 2;
                db jj = (used[p] - used[p - 1]) / len2;
                vec2.emplace_back(used[p - 1], used[p], gg, jj);
                p++;
            }
        }
    }
    sort(vec1.begin(), vec1.end());
    sort(vec2.begin(), vec2.end());

    // for (auto [l, r, x, k] : vec1){
    //     cout << l << ' ' << r << ' ' << x << ' ' << k << endl;
    // }
    // cout << endl;
    // for (auto [l, r, x, k] : vec2){
    //     cout << l << ' ' << r << ' ' << x << ' ' << k << endl;
    // }

    s[0] = vec2[0].x * vec2[0].k;
    ks[0] = vec2[0].k;
    for (int i = 1; i < vec2.size(); i++){
        s[i] = s[i - 1] + vec2[i].x * vec2[i].k;
        ks[i] = ks[i - 1] + vec2[i].k;
    }
    db sum = s[vec2.size()] = s[vec2.size() - 1];
    db ksum = ks[vec2.size()] = ks[vec2.size() - 1];

    p = 0;
    db ans = 0;
    for (auto [l, r, x, k] : vec1){
        while (p < vec2.size() && vec2[p].r <= l){
            p++;
        }
        // cout << p << ' ';
        if (!flag1 && !flag2 && p < vec2.size() && vec2[p].l == l){
            db res = (p ? ks[p - 1] * x - s[p - 1] : 0);
            res += (sum - s[p]) - (ksum - ks[p]) * x;
            res = res * k + k * vec2[p].k / 3 * (r - l);
            ans += res;
        }else{
            db res = 0;
            if (p){
                res += ks[p - 1] * x - s[p - 1];
                res += (sum - s[p - 1]) - (ksum - ks[p - 1]) * x;
                // cout << x << ' ' << ks[p - 1] << ' ' << s[p - 1] << ' ';
                //cout << sum - s[p - 1] << ' ' << ksum - ks[p - 1] << ' ';
            }else{
                res = sum - ksum * x;
            }
            ans += res * k;
            // cout << res * k << endl;
        }
    }

    cout << fixed << setprecision(20) << ans << endl;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
0 1
0 1

output:

0.33333333333333333334

result:

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

Test #2:

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

input:

1 1
0 1
1 1

output:

0.50000000000000000000

result:

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

Test #3:

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

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.66666666668606922030

result:

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

Test #4:

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

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000.00000000000000000000

result:

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

Test #5:

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

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

1000000000.00000000000000000000

result:

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

Test #6:

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

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

1000000000.50000000000000000000

result:

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

Test #7:

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

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

999999999.00000000046566128731

result:

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

Test #8:

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

input:

1 1
1000000000 1000000000
-1000000000 -1000000000

output:

2000000000.00000000000000000000

result:

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

Test #9:

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

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:

0.37773589269810423118

result:

wrong answer 1st numbers differ - expected: '6717.1171457', found: '0.3777359', error = '0.9999438'