QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#168932#4037. Absolute Pairwise Distancenhuang685WA 76ms4272kbC++207.3kb2023-09-09 05:52:592023-09-09 05:53:00

Judging History

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

  • [2023-09-09 05:53:00]
  • 评测
  • 测评结果：WA
  • 用时：76ms
  • 内存：4272kb
查看
  • [2023-09-09 05:52:59]
  • 提交

answer

/**
 * @file qoj4037-1.cpp
 * @author n685
 * @brief
 * @date 2023-09-06
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
std::ifstream cin;
std::ofstream cout;
using std::cerr;
#else
using std::cin;
using std::cout;
#define cerr                                                                   \
  if (false)                                                                   \
  std::cerr
#endif

#ifdef LOCAL
#include "dd/debug.h"
#define dbg(...) lineInfo(__LINE__, #__VA_ARGS__), dbg1(__VA_ARGS__)
#define dbgR(...) lineInfo(__LINE__, #__VA_ARGS__), dbg2(__VA_ARGS__)
#define dbgP(p, ...)                                                           \
  lineInfo(__LINE__, #__VA_ARGS__ " proj"), dbg3(p, __VA_ARGS__)
#define dbgRP(p, ...)                                                          \
  lineInfo(__LINE__, #__VA_ARGS__ " proj"), dbg4(p, __VA_ARGS__)
void nline() { cerr << '\n'; }
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif

template <class T> struct CC {
  std::vector<T> val;
  void push(T a) { val.push_back(a); }
  void init() {
    std::sort(val.begin(), val.end());
    val.erase(std::unique(val.begin(), val.end()), val.end());
  }
  int operator[](T a) const {
    return static_cast<int>(std::distance(
        val.begin(), std::lower_bound(val.begin(), val.end(), a)));
  }
  int size() const { return static_cast<int>(val.size()); }
};

#ifndef LOCAL
constexpr int B = 300;
#else
constexpr int B = 2;
#endif

template <class T> struct BIT {
  int sz;
  std::vector<T> val;
  BIT() : sz(0) {}
  BIT(int _sz) : sz(_sz), val(sz + 1) {}
  void add(int i, T a) {
    i++;
    for (; i <= sz; i += (i & -i)) {
      val[i] += a;
    }
  }
  T sum(int i) {
    i++;
    T ans = 0;
    for (; i > 0; i -= (i & -i)) {
      ans += val[i];
    }
    return ans;
  }
  T query(int a, int b) { return sum(b) - sum(a - 1); }
};
// upd: O(sqrt(N)), query: O(1)
template <class T> struct PURQ {
  int sz, bSz;
  std::vector<T> val, bl;
  PURQ(int _sz)
      : sz(_sz), bSz((_sz + B - 1) / B), val(_sz), bl((_sz + B - 1) / B) {}
  void add(int i, T a) {
    for (; i < sz && i % B != 0; ++i) {
      val[i] += a;
    }
    if (i == sz) {
      return;
    }
    i /= B;
    for (; i < bSz; ++i) {
      bl[i] += a;
    }
  }
  T sum(int i) {
    if (i < 0) {
      return 0;
    }
    return val[i] + bl[i / B];
  }
  T query(int a, int b) {
    if (a > b) {
      return 0;
    }
    return sum(b) - sum(a - 1);
  }
};

int n, q;
int m;
std::vector<int64_t> a;
std::vector<int> aa;

struct Q1 {
  int l = -1, r = -1;
  int ind = 0;
};
struct Q {
  int l1 = -1, r1 = -1, l2 = -1, r2 = -1;
  Q1 rr, rl, lr, ll;
};

namespace MO {
std::vector<Q1> qq;
std::vector<int64_t> ans;
void insert(Q1 &q) {
  q.ind = (int)qq.size() + 1;
  qq.push_back(q);
}
void init() {
  BIT<int64_t> v1(m), v2(m);
  BIT<int> f1(m), f2(m);
  int k = (int)qq.size();
  std::sort(qq.begin(), qq.end(), [&](auto a, auto b) {
    return (a.l / B == b.l / B) ? a.r < b.r : a.l < b.l;
  });
  ans.resize(k + 1);
  for (int i = 0; i <= qq[0].l; ++i) {
    v1.add(aa[i], a[i]);
    f1.add(aa[i], 1);
  }
  for (int i = 0; i <= qq[0].r; ++i) {
    ans[qq[0].ind] += (v1.query(aa[i], m - 1) - f1.query(aa[i], m - 1) * a[i]) +
                      (f1.query(0, aa[i] - 1) * a[i] - v1.query(0, aa[i] - 1));
    v2.add(aa[i], a[i]);
    f2.add(aa[i], 1);
  }
  for (int j = 1; j < k; ++j) {
    // transition from i - 1 to i
    ans[qq[j].ind] = ans[qq[j - 1].ind];
    bool ll = qq[j].l < qq[j - 1].l;
    bool rr = qq[j - 1].r < qq[j].r;
    if (ll) {
      for (int i = qq[j - 1].l; i > qq[j].l; --i) {
        ans[qq[j].ind] -=
            (v2.query(aa[i], m - 1) - f2.query(aa[i], m - 1) * a[i]) +
            (f2.query(0, aa[i] - 1) * a[i] - v2.query(0, aa[i] - 1));
        v1.add(aa[i], -a[i]);
        f1.add(aa[i], -1);
      }
      if (rr) {
        for (int i = qq[j - 1].r + 1; i <= qq[j].r; ++i) {
          ans[qq[j].ind] +=
              (v1.query(aa[i], m - 1) - f1.query(aa[i], m - 1) * a[i]) +
              (f1.query(0, aa[i] - 1) * a[i] - v1.query(0, aa[i] - 1));
          v2.add(aa[i], a[i]);
          f2.add(aa[i], 1);
        }
      } else {
        for (int i = qq[j - 1].r; i > qq[j].r; --i) {
          ans[qq[j].ind] -=
              (v1.query(aa[i], m - 1) - f1.query(aa[i], m - 1) * a[i]) +
              (f1.query(0, aa[i] - 1) * a[i] - v1.query(0, aa[i] - 1));
          v2.add(aa[i], -a[i]);
          f2.add(aa[i], -1);
        }
      }
    } else {
      if (rr) {
        for (int i = qq[j - 1].r + 1; i <= qq[j].r; ++i) {
          ans[qq[j].ind] +=
              (v1.query(aa[i], m - 1) - f1.query(aa[i], m - 1) * a[i]) +
              (f1.query(0, aa[i] - 1) * a[i] - v1.query(0, aa[i] - 1));
          v2.add(aa[i], a[i]);
          f2.add(aa[i], 1);
        }
      } else {
        for (int i = qq[j - 1].r; i > qq[j].r; --i) {
          ans[qq[j].ind] -=
              (v1.query(aa[i], m - 1) - f1.query(aa[i], m - 1) * a[i]) +
              (f1.query(0, aa[i] - 1) * a[i] - v1.query(0, aa[i] - 1));
          v2.add(aa[i], -a[i]);
          f2.add(aa[i], -1);
        }
      }
      if (ll) {
        for (int i = qq[j - 1].l; i > qq[j].l; --i) {
          ans[qq[j].ind] -=
              (v2.query(aa[i], m - 1) - f2.query(aa[i], m - 1) * a[i]) +
              (f2.query(0, aa[i] - 1) * a[i] - v2.query(0, aa[i] - 1));
          v1.add(aa[i], -a[i]);
          f1.add(aa[i], -1);
        }
      } else {
        for (int i = qq[j - 1].l + 1; i <= qq[j].l; ++i) {
          ans[qq[j].ind] +=
              (v2.query(aa[i], m - 1) - f2.query(aa[i], m - 1) * a[i]) +
              (f2.query(0, aa[i] - 1) * a[i] - v2.query(0, aa[i] - 1));
          v1.add(aa[i], a[i]);
          f1.add(aa[i], 1);
        }
      }
    }
  }
}
}; // namespace MO

int main() {
#ifdef LOCAL
  cin.open("input.txt");
  cout.rdbuf()->pubsetbuf(0, 0);
  cout.open("output.txt");
#else
  cin.tie(nullptr)->sync_with_stdio(false);
#endif

  cin >> n >> q;
  a.resize(n);
  CC<int64_t> cc;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    cc.push(a[i]);
  }
  cc.init();
  m = cc.size();
  aa.resize(n);
  for (int i = 0; i < n; ++i) {
    aa[i] = cc[a[i]];
  }
  std::vector<Q> qq(q);
  std::vector<Q1> q2;

  auto create = [&](int a, int b) {
    return Q1{std::min(a, b), std::max(a, b)};
  };
  for (int i = 0; i < q; ++i) {
    cin >> qq[i].l1 >> qq[i].r1 >> qq[i].l2 >> qq[i].r2;
    qq[i].l1--;
    qq[i].l2--;
    qq[i].r1--;
    qq[i].r2--;
    qq[i].rr = create(qq[i].r1, qq[i].r2);
    MO::insert(qq[i].rr);
    if (qq[i].l2 > 0) {
      qq[i].rl = create(qq[i].r1, qq[i].l2 - 1);
      MO::insert(qq[i].rl);
    }
    if (qq[i].l1 > 0) {
      qq[i].lr = create(qq[i].l1 - 1, qq[i].r1);
      MO::insert(qq[i].lr);
    }
    if (qq[i].l1 > 0 && qq[i].l2 > 0) {
      qq[i].ll = create(qq[i].l1 - 1, qq[i].l2 - 1);
      MO::insert(qq[i].ll);
    }
  }
  MO::init();
  std::vector<int64_t> ans(q);
  for (int i = 0; i < q; ++i) {
    ans[i] = MO::ans[qq[i].rr.ind] - MO::ans[qq[i].rl.ind] -
             MO::ans[qq[i].lr.ind] + MO::ans[qq[i].ll.ind];
    cout << ans[i] << '\n';
  }
}
源文件, 语言: C++20

詳細信息

Test #1:

score: 0
Wrong Answer
time: 76ms
memory: 4272kb

input:

3531 5803
74176369 34532623 97215138 20242270 85176324 44458100 86497709 71971680 57465677 61041230 69951857 80200098 11594209 20849868 84413937 93600227 54771865 31195982 73364328 72732309 10451014 71263803 72054056 97836493 40190962 6061330 8001777 68117678 61121864 54581549 85284322 23842874 6478...

output:

-97181848149953
45069990593773
54323257564444
7510065590746
65933654365002
18902476299191
-110247575312493
88916208460606
19270189659533
-2691615137072
-43018249323355
37500458946695
28018815784530
54468071906845
73334487021877
-30853198498549
-147558921689627
213870348247829
18968031484949
81195667...

result:

wrong answer 1st numbers differ - expected: '4982399918307', found: '-97181848149953'
English 繁體中文 简体中文

伺服器時間: 2024-12-02 12:39:01 | 開源專案