QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#149054#5433. Absolute DifferenceinvernoWA 2ms9908kbC++144.7kb2023-08-23 23:23:312023-08-23 23:23:35

Judging History

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

  • [2023-08-23 23:23:35]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9908kb
  • [2023-08-23 23:23:31]
  • 提交

answer

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

//typedef long double ld;
//typedef long long LL;

#define wr(l, x) cout << l << " " << x << endl

const int N = 100002;
struct rec{
    LL l, r;
};
rec a[N], b[N], c[N];
int n, m;    
LL S1, S2;
ld S12, S22;
ld ans, S23[N], S24[N];

//区间不交
inline bool cmp(rec a, rec b) {
    return a.l < b.l;
}
inline bool itrsct(int i, int j){
    return (min(a[i].r, b[j].r) - max(a[i].l, b[j].l)) >= 0;
}


inline ld calc1(LL a, LL b) {
    ld tmp = (b - a);
    return tmp * tmp / S1 / S2 * tmp / 3.0;
}

//[a,b] < [c,d]
inline ld calc0(LL a, LL b, LL c, LL d) {
    if (a == b || c == d) return 0;
    ld t1 = b - a, t2 = d - c;
    return ((ld)(d * d - c * c) / S1 / S2 * t1 - (ld)(b * b - a * a) / S1 / S2 * t2) / 2.0;
}

inline void calc(int i, int j) {
    LL l1 = a[i].l, r1 = a[i].r;
    LL l2 = b[j].l, r2 = b[j].r;
    LL l3 = max(l1, l2), r3 = min(r1, r2);
//    l1 r1
// l2 l3 r3 r2s
    ans += calc0(l1,l3,l3,r3);
    ans += calc0(l3,r3,r3,r1);

    ans += calc0(l2,l3,l3,r3);
    ans += calc0(l3,r3,r3,r2);

    ans += calc0(l1,l3,r3,r2);
    ans += calc0(l2,l3,r3,r1);

    ans += calc1(l3,r3);
    return ;
}

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

    LL l, r;
    cin >> n >> m;
    for (int i = 1;i <= n;++ i){
        cin >> l >> r;
        a[i] = (rec){l,r};
        if (r < l) cout << "Failed\n";
        S1 += r-l;
    }
    for (int i = 1;i <= m;++ i) {
        cin >> l >>  r;
        b[i] = (rec){l,r};
        if (r < l) cout << "Failed\n";
        S2 += r-l;
    }
    cout << "---== \n";
    sort(a + 1, a + 1 + n, cmp);
    sort(b + 1, b + 1 + m, cmp);
    if (S1 != 0 && S2 == 0) {
        swap(S1, S2);
        for (int i = 1;i <= n;++ i) 
          c[i] = a[i];
        for (int i = 1;i <= m;++ i) 
          a[i] = b[i];
        for (int i = 1;i <= n;++ i)
          b[i] = c[i];
        swap(n,m);
    }

    if (S1 == 0 && S2 != 0) {
       for (int i = 1;i <= m;++ i) {
         S23[i] = S23[i - 1] - (ld)(b[i].r * b[i].r - b[i].l * b[i].l) / S2 / n / 2;
         S24[i] = S24[i - 1] + (ld)(b[i].r - b[i].l) / S2 / n;
       }
       for (int i = 1;i <= n;++ i) {
          int k = upper_bound(b + 1, b + m + 1, a[i], cmp) - b;
          -- k;
          ans += (2 * S23[k] - S23[m]);
          ans += (2 * S24[k] - S24[m]) * a[i].l;
          if (b[k].l <= a[i].l && a[i].l <= b[k].r) {
              ans += (ld)(a[i].l - b[k].l) * (a[i].l - b[k].l) / S2 / n / 2;
              ans += (ld)(b[k].r - a[i].l) * (b[k].r - a[i].l) / S2 / n / 2;

              ans += (ld)(b[k].r * b[k].r - b[k].l * b[k].l) / S2 / n / 2;
              ans -= (ld)(b[k].r - b[k].l) / S2 / n * a[i].l;
          } 
          //else ans += S23[k] + S24[k] * a[i].l;
       }
       cout << fixed << setprecision(10) << ans << endl;
       return 0;
    }
    if (S1 == 0 && S2 == 0) {
       for (int i = 1;i <= m;++ i) {
         S23[i] = S23[i - 1] + b[i].l;
       }
       for (int i = 1;i <= n;++ i) {
          int k = upper_bound(b + 1, b + m + 1, a[i], cmp) - b;
          -- k;
          ans += (ld)a[i].l * (k - (m - k)) / n / m;
          ans += (- S23[k] - S23[k] + S23[m]) / n / m;
       }
       cout << fixed << setprecision(10) << ans << endl;
       return 0;
    } 

    for (int i = 1;i <= n;++ i){
        l = a[i].l, r = a[i].r;
        S12 += (ld)(r * r - l * l)/S1/S2;
    }
    for (int i = 1;i <= m;++ i) {
        l = b[i].l, r = b[i].r;
        S22 += (ld)(r * r - l * l)/S1/S2;
    }

    int i = 1, j = 1;
    LL lsum = 0, rsum = 0;
    ld lsum2 = 0, rsum2 = 0;
    while (i <= n) {
        LL ssum = 0;
        ld ssum2 = 0; 
        while (j <= m && b[j].l < a[i].r && !itrsct(i,j)) {
            lsum += b[j].r - b[j].l;
            lsum2 += (ld)(b[j].r * b[j].r - b[j].l * b[j].l)/S1/S2;
            ++ j;
        }
        while (j <= m && itrsct(i, j)) {
            calc(i, j);
            ssum += b[j].r - b[j].l;
            ssum2 += (ld)(b[j].r * b[j].r - b[j].l * b[j].l)/S1/S2;
            ++ j;
        }
        rsum = S2 - (lsum + ssum);
        rsum2 = S22 - (lsum2 + ssum2);

        LL ival = a[i].r - a[i].l;
        ld ival2 = a[i].r * a[i].r - a[i].l * a[i].l;
        ans += (lsum * (ival2/S1/S2) - lsum2       * ival) / 2.0;
        ans += (ival * rsum2       - (ival2/S1/S2) * rsum) / 2.0;
        
        lsum += ssum;  lsum2 += ssum2;
        ++ i;
        if (itrsct(i, j - 1)){
            -- j;
            lsum -= b[j].r - b[j].l;
            lsum2 -= (ld)(b[j].r * b[j].r - b[j].l * b[j].l)/S1/S2;
        }
    }
    cout << fixed << setprecision(10) << ans << endl;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 9908kb

input:

1 1
0 1
0 1

output:

---== 
0.3333333333

result:

wrong output format Expected double, but "---==" found