QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#764190#5433. Absolute DifferencefosovWA 0ms3876kbC++142.5kb2024-11-20 05:13:102024-11-20 05:13:10

Judging History

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

  • [2024-11-20 05:13:10]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3876kb
  • [2024-11-20 05:13:10]
  • 提交

answer

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

#define ll long long 
#define lll __int128
#define INF 0x3f3f3f3f
#define LNF 0x3f3f3f3f3f3f3f3fll
#define MOD 998244353
#define pii pair<int, int>
#define ld long double
#define fi first
#define se second
#define all(a) a.begin(), a.end()

#define N 20


int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << setprecision(18);

    int n, m; cin >> n >> m;

    vector<pii> a(n), b(m);
    ll ca = 0, cb = 0;
    for (int i = 0; i < n; ++ i) cin >> a[i].fi >> a[i].se, ca += a[i].se - a[i].fi;
    for (int i = 0; i < m; ++ i) cin >> b[i].fi >> b[i].se, cb += b[i].se - b[i].fi;
    sort(all(a)), sort(all(b));

    auto pa = [&](int l, int r) {
        return ca ? (ld) (r - l) / ca : (ld) 1 / n;
    };
    auto pb = [&](int l, int r) {
        return cb ? (ld) (r - l) / cb : (ld) 1 / m;
    };
    auto w = [&](int l, int r) {
        return l + (ld) (r - l) / 2;
    };

    ld sum = 0;
    for (int i = 0; i < m; ++ i) sum += w(b[i].fi, b[i].se) * pb(b[i].fi, b[i].se);

    ld sl = 0, sr = 0, res = 0;
    for (int i = 0, l = 0, r = 0; i < n; ++ i) {
        while (l < n && b[l].se < a[i].fi) sl += w(b[i].fi, b[i].se) * pb(b[i].fi, b[i].se), ++ l;
        while (r < n && b[r].fi <= a[i].se) sr += w(b[i].fi, b[i].se) * pb(b[i].fi, b[i].se), ++ r;

        res += w(a[i].fi, a[i].se) * pa(a[i].fi, a[i].se) * l - sl;
        res += (sum - sr) - w(a[i].fi, a[i].se) * pa(a[i].fi, a[i].se) * (n-r);

        queue<pii> cur;
        for (int j = l; j < r; ++ j) cur.emplace(b[j]);
        while (!cur.empty()) {
            auto [cl, cr] = cur.front(); cur.pop();
            if (cl == a[i].fi && cr == a[i].se) {
                ld d = a[i].se - a[i].fi;
                res += d * pa(cl, cr) * pb(cl, cr) / 3;
                continue;
            }
            if (max(cl, a[i].fi) < min(cr, a[i].se)) {
                cur.emplace(cl, a[i].fi);
                cur.emplace(a[i].se, cr);
                cur.emplace(max(cl, a[i].fi), min(cr, a[i].se));
                continue;
            }
            if (cr <= a[i].fi) {
                res += w(a[i].fi, a[i].se) * pa(a[i].fi, a[i].se) - w(cl, cr) * pb(cl, cr); 
                continue;
            }
            if (cl >= a[i].se) {
                res += w(cl, cr) * pb(cl, cr) - w(a[i].fi, a[i].se) * pa(a[i].fi, a[i].se);
                continue;
            }
        }
    }

    cout << res << '\n';
}   

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
0 1
0 1

output:

0.333333333333333333

result:

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

Test #2:

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

input:

1 1
0 1
1 1

output:

0.5

result:

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

Test #3:

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

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.666666667

result:

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

Test #4:

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

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000

result:

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

Test #5:

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

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

1000000000

result:

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

Test #6:

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

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

1000000000.5

result:

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

Test #7:

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

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

0

result:

wrong answer 1st numbers differ - expected: '999999999.0000000', found: '0.0000000', error = '1.0000000'