QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#400910#5433. Absolute Differencecomeintocalm#WA 1ms3884kbC++173.1kb2024-04-27 18:06:482024-04-27 18:06:49

Judging History

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

  • [2024-04-27 18:06:49]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3884kb
  • [2024-04-27 18:06:48]
  • 提交

answer

#include <bits/stdc++.h>

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  std::vector<std::pair<int,int>> a(n), b(m);
  std::vector<std::pair<int,int>> sa, sb;
  bool fa = false, fb = false;
  for (auto &[x, y] : a) {
    scanf("%d%d", &x, &y);
    if (x != y) {
      fa = true;
    }
  }
  for (auto &[x, y] : b) {
    scanf("%d%d", &x, &y);
    if (x != y) {
      fb = true;
    }
  }
  std::sort(a.begin(), a.end());
  std::sort(b.begin(), b.end());
  int l = -1;
  for (auto &&[x, y]: a) {
    int r = l;
    while (r < m && b[r + 1].first < y) {
      ++r;
    }
    for (int i = l + 1; i <= r; ++i) {
      if (b[i].second <= x) {
        sa.emplace_back(b[i]);
        ++l;
      }
      if (b[i].first < x) {
        sb.emplace_back(b[i].first, x);
        b[i].first = x;
      }
      if (b[i].first > x) {
        sa.emplace_back(x, b[i].first);
        x = b[i].first;
      }
      if (b[i].second > x) {
        sa.emplace_back(x, y);
        sb.emplace_back(x, y);
        x = y;
        b[i].first = y;
      } else {
        sa.emplace_back(b[i]);
        sb.emplace_back(b[i]);
        x = b[i].second;
        b[i].first = b[i].second;
        ++l;
      }
    }
  }
  long double ans = 0;
  n = sa.size(), m = sb.size();
  std::vector<long long> prea, pre1(n), pre2(n);

  auto get = [] (int l, int r, std::vector<long long> &pre) -> long long {
    if (l > r) {
      return 0;
    }
    if (l == 0) {
      return pre[r];
    }
    return pre[r] - pre[l - 1];
  };

  if (!fa && fb) {
    std::swap(fa, fb);
    std::swap(a, b);
  }
  if (!fb) {
    n = a.size();
    prea.assign(n, 0);
    for (int i = 0; i < n; ++i) {
      prea[i] = (a[i].second + a[i].first);
      if (i > 0) {
        prea[i] += prea[i - 1];
      }
    }
    // puts("q");
    for (auto &[l1, r1]: b) {
      int p = std::lower_bound(a.begin(), a.end(), std::make_pair(l1, r1)) - a.begin();
      // printf("p %d\n", p);
      ans += (1ll * (p) * l1 - get(0, p - 1, prea) / 2.0);
      if (p < m) {
        ans += (get(p, m - 1, prea) / 2.0 - 1ll * (m - p) * l1);
      }
    }
  } else {
    for (int i = 0; i < n; ++i) {
      pre1[i] = (sa[i].second - sa[i].first);
      pre2[i] = 1ll * sa[i].second * sa[i].second - 1ll * sa[i].first * sa[i].first;
      if (i > 0) {
        pre1[i] += pre1[i - 1];
        pre2[i] += pre2[i - 1];
      }
    }
    for (auto &[l1, r1]: sb) {
      int p = std::lower_bound(sa.begin(), sa.end(), std::make_pair(l1, r1)) - sa.begin();
      auto &[l2, r2] = sa[p];
      bool flag = false;
      if (l1 == l2 && r1 == r2) {
        ans += (r1 - l1) / 3.0;
        ++p;
        flag = true;
      }
      if (p < m) {
        ans += ((r1 - l1) * get(p - 1, m - 1, pre2) - (1ll * r1 * r1 - 1ll * l1 * l1) * get(p - 1, m - 1, pre1)) / 2.0;
      }
      if (flag) {
        --p;
      }
      --p;
      if (p >= 0) {
        ans += ((r1 - l1) * get(0, p - 1, pre2) - (1ll * r1 * r1 - 1ll * l1 * l1) * get(p - 1, m - 1, pre1)) / 2.0;
      }
    }
  }
  printf("%.16Lf\n", ans);
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3884kb

input:

1 1
0 1
0 1

output:

0.1666666666666667

result:

wrong answer 1st numbers differ - expected: '0.3333333', found: '0.1666667', error = '0.1666667'