QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#148748#5433. Absolute DifferenceinvernoWA 2ms10060kbC++144.6kb2023-08-23 18:29:282023-08-23 20:27:03

Judging History

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

  • [2023-08-23 20:27:03]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10060kb
  • [2023-08-23 18:29:28]
  • 提交

answer

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

#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};
        S1 += r-l;
    }
    for (int i = 1;i <= m;++ i) {
        cin >> l >> r;
        b[i] = (rec){l,r};
        S2 += r-l;
    }
    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;
}

详细

Test #1:

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

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: 1ms
memory: 8016kb

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: 2ms
memory: 9980kb

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.6666666666

result:

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

Test #4:

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

input:

1 1
-1000000000 0
0 1000000000

output:

1000000000.0000000000

result:

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

Test #5:

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

input:

1 1
-1000000000 -1000000000
-1000000000 1000000000

output:

1000000000.0000000000

result:

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

Test #6:

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

input:

1 1
-999999999 1000000000
-1000000000 -1000000000

output:

1000000000.5000000000

result:

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

Test #7:

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

input:

1 1
-1000000000 1000000000
-999999999 -999999999

output:

999999999.0000000005

result:

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

Test #8:

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

input:

1 1
1000000000 1000000000
-1000000000 -1000000000

output:

2000000000.0000000000

result:

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

Test #9:

score: -100
Wrong Answer
time: 2ms
memory: 7944kb

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.1170590434

result:

wrong answer 1st numbers differ - expected: '6717.1171457', found: '6717.1170590', error = '0.0000000'