QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#682922#5433. Absolute DifferencejieloscWA 2ms6488kbC++203.5kb2024-10-27 17:56:312024-10-27 17:56:32

Judging History

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

  • [2024-10-27 17:56:32]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:6488kb
  • [2024-10-27 17:56:31]
  • 提交

answer

#include <bits/stdc++.h>
#define int int64_t

using std::cin;
using std::cout;
const char endl = '\n';

struct interval {
  double l, r;
};
auto a = std::vector<interval>((int)1.1E5);
auto b = std::vector<interval>((int)1.1E5);

struct frac {
  int up, down;
};

frac pre[(int)1.1E5];
frac suf[(int)1.1E5];

// double f1(double lx, double rx, double y) {
//   return ((rx * rx - lx * lx) * y - (rx - lx) * y * y) / 2;
// }
// double f2(double lx, double rx, double y) {
//   return y * y * y / 3 + (lx + rx) * y * y / 2 + (lx * lx + rx * rx) * y / 2;
// }
// double f3(double lx, double rx, double y) {
//   return -f1(lx, rx, y);
// }

double calc(double lx, double rx, double ly, double ry) {
  auto f1 = [&](double y) -> double {
    return ((rx * rx - lx * lx) * y - (rx - lx) * y * y) / 2;
  };
  auto f2 = [&](double y) -> double {
    return y * y * y / 3 - (lx + rx) * y * y / 2 + (lx * lx + rx * rx) * y / 2;
  };
  auto f3 = [&](double y) -> double { return -f1(y); };

  if (ly < lx) {
    if (ry <= rx) return f1(lx) - f1(ly) + f2(ry) - f2(lx);
    return f1(lx) - f1(ly) + f2(rx) - f2(lx) + f3(ry) - f3(rx);
  }
  if (ry <= rx) return f2(ry) - f2(ly);
  return f2(rx) - f2(ly) + f3(ry) - f3(rx);
}

void solve() {
  int n, m;
  cin >> n >> m;
  int len_a = 0, len_b = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i].l >> a[i].r, len_a += a[i].r - a[i].l;
    // if (a[i].l == a[i].r) a[i].r += 1E-10;
  }
  for (int i = 1; i <= m; ++i) {
    cin >> b[i].l >> b[i].r, len_b += b[i].r - b[i].l;
    // if (b[i].l == b[i].r) b[i].r += 1E-10;
  }
  if (len_b == 0) {
    std::swap(a, b);
    std::swap(n, m);
    std::swap(len_a, len_b);
  }
  // if(len_a == 0) {
  //   auto pre = std::vector<double>(m + 10);
  //   auto suf = pre;
  //   if(len_b == 0) {
  //     for(int i = 1; i <= m; ++i) pre[i] = pre[i]
  //   }
  // }
  for (int i = 1; i <= m; ++i) {
    if (len_b == 0) {
      pre[i].up = pre[i - 1].up + (int)1E9 - b[i].l;
      pre[i].down = pre[i - 1].down + 1;
    } else {
      pre[i].up =
        pre[i - 1].up + (int)2E9 - (b[i].l + b[i].r) * (b[i].r - b[i].l);
      pre[i].down = pre[i - 1].down + (b[i].r - b[i].l) * 2;
    }
  }
  for (int i = m; i >= 1; --i) {
    if (len_b == 0) {
      suf[i].up = suf[i + 1].up + b[i].l + (int)1E9;
      suf[i].down = suf[i + 1].down + 1;
    } else {
      suf[i].up =
        suf[i + 1].up + (b[i].l + b[i].r) * (b[i].r - b[i].l) + (int)2E9;
      suf[i].down = suf[i + 1].down + (b[i].r - b[i].l) * 2;
    }
  }
  double ans = 0;
  for (int i = 1, j = 1; i <= n; ++i) {
    double sum = 0;
    double mid = (a[i].l + a[i].r) / 2.0;
    while (j <= m and b[j].r <= a[i].l) ++j;
    if (pre[j - 1].down)
      sum += (double)pre[j - 1].up / pre[j - 1].down - (1E9 - mid);
    while (j <= m and b[j].l < a[i].r) {
      sum += calc(a[i].l, a[i].r, b[j].l, b[j].r);
      ++j;
    }
    if (suf[j].down) sum += (double)suf[j].up / suf[j].down - (mid + 1E9);
    if (a[i].r - a[i].l) ans += sum / (a[i].r - a[i].l);
    if (len_a == 0) ans += sum;
  }
  cout << std::fixed;
  cout << std::setprecision(12);
  if (len_a == 0) len_a = n;
  cout << ans / len_a << endl;
}

int32_t main() {
#ifndef _DEBUG
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif
  int tc = 1;
  // std::cin >> tc;
  while (tc--) solve();
#ifdef _DEBUG
  std::cout << std::endl;
  std::cout << "Time used: " << clock() << "ms" << std::endl;
  system("pause");
  return 0;
#endif
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

1 1
-1000000000 1000000000
-1000000000 1000000000

output:

666666666.666666626930

result:

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

Test #4:

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

input:

1 1
-1000000000 0
0 1000000000

output:

0.000000000000

result:

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