結果

問題 No.2873 Kendall's Tau
ユーザー lmorilmori
提出日時 2024-10-15 02:18:36
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 14,868 bytes
コンパイル時間 4,858 ms
コンパイル使用メモリ 313,172 KB
実行使用メモリ 52,480 KB
最終ジャッジ日時 2024-10-15 02:19:04
合計ジャッジ時間 26,308 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 3 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 335 ms
18,176 KB
testcase_14 WA -
testcase_15 AC 178 ms
11,392 KB
testcase_16 AC 186 ms
11,904 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 193 ms
11,904 KB
testcase_21 WA -
testcase_22 AC 274 ms
15,488 KB
testcase_23 WA -
testcase_24 AC 83 ms
7,040 KB
testcase_25 AC 171 ms
11,008 KB
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 AC 129 ms
9,216 KB
testcase_31 AC 297 ms
15,104 KB
testcase_32 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma region Macros
#include <bits/stdc++.h>

using namespace std;
using lint = long long;
using ull = unsigned long long;
using ld = long double;
using int128 = __int128_t;
#define all(x) (x).begin(), (x).end()
#define EPS 1e-8
#define uniqv(v) v.erase(unique(all(v)), v.end())
#define OVERLOAD_REP(_1, _2, _3, name, ...) name
#define REP1(i, n) for (auto i = std::decay_t<decltype(n)>{}; (i) != (n); ++(i))
#define REP2(i, l, r) for (auto i = (l); (i) != (r); ++(i))
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
#define log(x) cout << x << endl
#define logfixed(x) cout << fixed << setprecision(15) << x << endl;
#define logy(bool)         \
  if (bool) {              \
    cout << "Yes" << endl; \
  } else {                 \
    cout << "No" << endl;  \
  }

ostream &operator<<(ostream &dest, __int128_t value) {
  ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(ios_base::badbit);
    }
  }
  return dest;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (int i = 0; i < (int)v.size(); i++) {
    os << v[i] << (i + 1 != (int)v.size() ? " " : "");
  }
  return os;
}

template <typename T>
ostream &operator<<(ostream &os, const set<T> &set_var) {
  for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
    os << *itr;
    ++itr;
    if (itr != set_var.end()) os << " ";
    itr--;
  }
  return os;
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &map_var) {
  for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
    os << itr->first << " -> " << itr->second << "\n";
  }
  return os;
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pair_var) {
  os << "(" << pair_var.first << ", " << pair_var.second << ")";
  return os;
}

void out() { cout << '\n'; }
template <class T, class... Ts>
void out(const T &a, const Ts &...b) {
  cout << a;
  (cout << ... << (cout << ' ', b));
  cout << '\n';
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &in : v) is >> in;
  return is;
}

inline void in(void) { return; }
template <typename First, typename... Rest>
void in(First &first, Rest &...rest) {
  cin >> first;
  in(rest...);
  return;
}

template <typename T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

vector<lint> dx8 = {1, 1, 0, -1, -1, -1, 0, 1};
vector<lint> dy8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<lint> dx4 = {1, 0, -1, 0};
vector<lint> dy4 = {0, 1, 0, -1};

template <class T>
class BitVector {
 private:
  unsigned n, cur, p;
  vector<unsigned> acc, bit;
  vector<T> srsum;

 public:
  BitVector() {
  }

  BitVector(vector<bool> &b) {
    cur = 0;
    n = b.size();
    acc.resize((n >> 5) + 2, 0);
    bit.resize((n >> 5) + 2, 0);
    srsum.resize(n + 1, 0);
    for (int i = 0; i < n; i++) {
      if (!(i & 31)) {
        cur++;
        acc[cur] = acc[cur - 1];
      }
      if (b[i]) {
        acc[cur] += int(b[i]);
        bit[cur - 1] |= (1U << (32 - (i & 31) - 1));
      }
    }
  }

  inline void srsum_set(const vector<T> &v) {
    for (int i = 0; i < n; i++) {
      srsum[i + 1] = srsum[i] + v[i];
    }
  }

  inline unsigned rank(unsigned k) {
    if (!(k & 31)) return acc[k >> 5];
    return acc[k >> 5] + __builtin_popcount(bit[k >> 5] >> (32 - (k & 31)));
  }

  inline T rank_srsum(unsigned k) {
    return srsum[k];
  }

  inline bool access(unsigned k) {
    return (rank(k + 1) - rank(k)) == 1;
  }
};

template <class T>
class WaveletMatrix {
 private:
  unsigned n;
  unsigned bitsize;
  vector<BitVector<T>> b;
  vector<unsigned> zero;
  vector<int> stInd;
  vector<unsigned> compressed;
  vector<T> cmp, px;
  vector<long long> sum;
  T MI, MA;

  // v[l,r) の中で値がk未満の総和を返す
  long long rank_sum(unsigned l, unsigned r, unsigned k) {
    long long less_sum = 0;
    for (unsigned i = 0; i < bitsize and l < r; i++) {
      const unsigned rank1_l = b[i].rank(l);
      const unsigned rank1_r = b[i].rank(r);
      const unsigned rank0_l = l - rank1_l;
      const unsigned rank0_r = r - rank1_r;
      if (k & (1U << (bitsize - i - 1))) {
        less_sum += b[i].rank_srsum(rank0_r) - b[i].rank_srsum(rank0_l);
        l = zero[i] + rank1_l;
        r = zero[i] + rank1_r;
      } else {
        l = rank0_l;
        r = rank0_r;
      }
    }
    return less_sum;
  }

  // v[l,r) の中で値がk未満の個数を返す
  unsigned rank_less(unsigned l, unsigned r, T k) {
    unsigned less = 0;
    for (unsigned i = 0; i < bitsize and l < r; i++) {
      const unsigned rank1_l = b[i].rank(l);
      const unsigned rank1_r = b[i].rank(r);
      const unsigned rank0_l = l - rank1_l;
      const unsigned rank0_r = r - rank1_r;
      if (k & (1U << (bitsize - i - 1))) {
        less += (rank0_r - rank0_l);
        l = zero[i] + rank1_l;
        r = zero[i] + rank1_r;
      } else {
        l = rank0_l;
        r = rank0_r;
      }
    }
    return less;
  }

  // v[l,r) の中で値がk未満の個数と総和を返す
  pair<long long, long long> rank_less_sum(unsigned l, unsigned r, T k) {
    long long less = 0;
    long long less_sum = 0;
    for (unsigned i = 0; i < bitsize and l < r; i++) {
      const unsigned rank1_l = b[i].rank(l);
      const unsigned rank1_r = b[i].rank(r);
      const unsigned rank0_l = l - rank1_l;
      const unsigned rank0_r = r - rank1_r;
      if (k & (1U << (bitsize - i - 1))) {
        less += (rank0_r - rank0_l);
        less_sum += b[i].rank_srsum(rank0_r) - b[i].rank_srsum(rank0_l);
        l = zero[i] + rank1_l;
        r = zero[i] + rank1_r;
      } else {
        l = rank0_l;
        r = rank0_r;
      }
    }
    return {less, less_sum};
  }

  inline unsigned compress(const T &x) {
    return lower_bound(cmp.begin(), cmp.end(), x) - begin(cmp);
  }

 public:
  // コンストラクタ
  WaveletMatrix() {}
  WaveletMatrix(vector<T> v) {
    MI = numeric_limits<T>::min();
    MA = numeric_limits<T>::max();
    n = v.size();
    cmp = v;
    sort(cmp.begin(), cmp.end());
    cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
    compressed.resize(n);
    sum.resize(n + 1);
    vector<T> tmp(n);
    vector<unsigned> tmpc(n);
    unsigned size_mx = v.size();
    for (unsigned i = 0; i < n; i++) {
      compressed[i] = distance(cmp.begin(), lower_bound(cmp.begin(), cmp.end(), v[i]));
      sum[i + 1] = sum[i] + v[i];
    }
    stInd.resize(cmp.size() + 1, -1);
    bitsize = bit_width(size_mx);
    b.resize(bitsize);
    zero.resize(bitsize, 0);
    vector<bool> bit(n, 0);
    for (unsigned i = 0; i < bitsize; i++) {
      for (unsigned j = 0; j < n; j++) {
        bit[j] = compressed[j] & (1U << (bitsize - i - 1));
        zero[i] += unsigned(!bit[j]);
        tmp[j] = v[j];
        tmpc[j] = compressed[j];
      }
      b[i] = BitVector<T>(bit);
      int cur = 0;
      for (unsigned j = 0; j < n; j++) {
        if (!bit[j]) {
          v[cur] = tmp[j];
          compressed[cur] = tmpc[j];
          cur++;
        }
      }
      for (unsigned j = 0; j < n; j++) {
        if (bit[j]) {
          v[cur] = tmp[j];
          compressed[cur] = tmpc[j];
          cur++;
        }
      }
      b[i].srsum_set(v);
    }

    for (unsigned i = 0; i < n; i++) {
      if (stInd[compressed[i]] == -1) {
        stInd[compressed[i]] = i;
      }
    }
  }

  WaveletMatrix(vector<T> x, vector<T> y, vector<T> w) {
    n = x.size();
    px.resize(n);
    vector<tuple<T, T, T>> v(n);
    for (int i = 0; i < n; i++) {
      v[i] = {x[i], y[i], w[i]};
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < n; i++) {
      px[i] = get<0>(v[i]);
      y[i] = get<1>(v[i]);
      w[i] = get<2>(v[i]);
    }
    cmp.resize(y.size());
    cmp = y;
    sort(cmp.begin(), cmp.end());
    cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
    compressed.resize(n);
    vector<unsigned> tmp(n), tmpc(n);
    unsigned size_mx = y.size();
    for (unsigned i = 0; i < n; i++) {
      compressed[i] = distance(cmp.begin(), lower_bound(cmp.begin(), cmp.end(), y[i]));
    }
    stInd.resize(cmp.size() + 1, -1);
    bitsize = bit_width(size_mx);
    b.resize(bitsize);
    zero.resize(bitsize, 0);
    vector<bool> bit(n, 0);
    for (unsigned i = 0; i < bitsize; i++) {
      for (unsigned j = 0; j < n; j++) {
        bit[j] = compressed[j] & (1U << (bitsize - i - 1));
        zero[i] += unsigned(!bit[j]);
        tmp[j] = w[j];
        tmpc[j] = compressed[j];
      }
      b[i] = BitVector<T>(bit);
      int cur = 0;
      for (unsigned j = 0; j < n; j++) {
        if (!bit[j]) {
          w[cur] = tmp[j];
          compressed[cur] = tmpc[j];
          cur++;
        }
      }
      for (unsigned j = 0; j < n; j++) {
        if (bit[j]) {
          w[cur] = tmp[j];
          compressed[cur] = tmpc[j];
          cur++;
        }
      }
      b[i].srsum_set(w);
    }
    for (unsigned i = 0; i < n; i++) {
      if (stInd[compressed[i]] == -1) {
        stInd[compressed[i]] = i;
      }
    }
  }

  // get v[k]
  T access(unsigned k) {
    unsigned res = 0;
    unsigned cur = k;
    for (unsigned i = 0; i < bitsize; i++) {
      if (b[i].access(cur)) {
        res |= (1U << (bitsize - i - 1));
        cur = zero[i] + b[i].rank(cur);
      } else {
        cur -= b[i].rank(cur);
      }
    }
    return cmp[res];
  }

  // v[0,k) 中でのcの出現回数を返す
  unsigned rank(unsigned k, T c) {
    c = compress(c);
    unsigned cur = k;
    if (stInd[c] == -1) {
      return 0;
    }
    for (unsigned i = 0; i < bitsize; i++) {
      if (c & (1U << (bitsize - i - 1))) {
        cur = zero[i] + b[i].rank(cur);
      } else {
        cur -= b[i].rank(cur);
      }
    }
    return cur - stInd[c];
  }

  // v[l,r) の中でk番目(1-origin)に小さい値を返す
  T kth_smallest(unsigned l, unsigned r, unsigned k) {
    unsigned res = 0;
    for (unsigned i = 0; i < bitsize; i++) {
      unsigned num1 = b[i].rank(r) - b[i].rank(l);
      unsigned num0 = r - l - num1;
      if (num0 < k) {
        res |= (1ULL << (bitsize - i - 1));
        l = zero[i] + b[i].rank(l);
        r = zero[i] + b[i].rank(r);
        k -= num0;
      } else {
        l -= b[i].rank(l);
        r -= b[i].rank(r);
      }
    }
    return cmp[res];
  }

  // v[l,r) の中でk番目(1-origin)に大きい値を返す
  T kth_largest(unsigned l, unsigned r, unsigned k) {
    return kth_smallest(l, r, r - l - k + 1);
  }

  // v[l,r]を昇順ソートした時の先頭k個の総和を返す
  long long kth_ascending_sum(unsigned l, unsigned r, unsigned k) {
    long long res = 0;
    unsigned val = 0;
    for (unsigned i = 0; i < bitsize; i++) {
      const unsigned rank1_l = b[i].rank(l);
      const unsigned rank1_r = b[i].rank(r);
      const unsigned rank0_l = l - rank1_l;
      const unsigned rank0_r = r - rank1_r;
      const unsigned num1 = rank1_r - rank1_l;
      const unsigned num0 = rank0_r - rank0_l;
      if (num0 < k) {
        val |= (1ULL << (bitsize - i - 1));
        res += b[i].rank_srsum(rank0_r) - b[i].rank_srsum(rank0_l);
        l = zero[i] + rank1_l;
        r = zero[i] + rank1_r;
        k -= num0;
      } else {
        l = rank0_l;
        r = rank0_r;
      }
    }
    res += int64_t(cmp[val]) * (k);
    return res;
  }

  // v[l,r]を降順ソートした時の先頭k個の総和を返す
  long long kth_descending_sum(unsigned l, unsigned r, unsigned k) {
    return range_sum(l, r) - kth_ascending_sum(l, r, r - l - k);
  }

  // v[l,r) の中で[mink,maxk)に入る値の個数を返す
  unsigned range_freq(unsigned l, unsigned r, T mink, T maxk) {
    mink = compress(mink);
    maxk = compress(maxk);
    if (mink == 0) {
      return rank_less(l, r, maxk);
    }
    return rank_less(l, r, maxk) - rank_less(l, r, mink);
  }

  // v[l,r) の総和を返す
  long long range_sum(unsigned l, unsigned r) {
    return sum[r] - sum[l];
  }

  // v[l,r) の中で[mink,maxk)に入る値の総和を返す
  long long range_sum(unsigned l, unsigned r, T mink, T maxk) {
    mink = compress(mink);
    maxk = compress(maxk);
    return rank_sum(l, r, maxk) - rank_sum(l, r, mink);
  }

  // v[l,r) の中で ∑|v[i]-d| を計算して返す
  long long range_abs(unsigned l, unsigned r, T d) {
    T dnum = rank(r, d) - rank(l, d);
    T dsum = d * dnum;
    T asum = range_sum(l, r);
    auto p = rank_less_sum(l, r, compress(d));
    T less = p.first;
    T less_sum = p.second;
    T more = r - l - dnum - less;
    T more_sum = asum - dsum - less_sum;
    return d * less + more_sum - less_sum - (d * more);
  }

  // v[l,r)の中でvalを超えない最大の値を返す
  T prev_value(unsigned l, unsigned r, T val) {
    int num = range_freq(l, r, MI, val);
    if (num == 0) {
      return MA;
    } else {
      return kth_smallest(l, r, num);
    }
  }

  // v[l,r)の中でval以上の最小の値を返す
  T next_value(unsigned l, unsigned r, T val) {
    int num = range_freq(l, r, MI, val);
    if (num == r - l) {
      return MI;
    } else {
      return kth_smallest(l, r, num + 1);
    }
  }

  // x座標が[l,r) かつy座標が[d,u) に入る点の個数を返す
  T rectangle_freq(T l, T r, T d, T u) {
    l = distance(px.begin(), lower_bound(px.begin(), px.end(), l));
    r = distance(px.begin(), lower_bound(px.begin(), px.end(), r));
    return range_freq(l, r, d, u);
  }

  // x座標が[l,r) かつy座標が[d,u) に入る点の総和を返す
  long long rectangle_sum(T l, T r, T d, T u) {
    l = distance(px.begin(), lower_bound(px.begin(), px.end(), l));
    r = distance(px.begin(), lower_bound(px.begin(), px.end(), r));
    return range_sum(l, r, d, u);
  }
};

int main() {
  lint INF = 1e9 + 10;
  cin.tie(0);

  ios::sync_with_stdio(false);
  int n;
  in(n);
  vector<lint> x(n), y(n), o(n);
  rep(i, n) {
    in(x[i], y[i]);
  }
  WaveletMatrix<lint> w(x, y, o);
  lint p, q, r, s;
  p = q = r = s = 0;
  rep(i, n) {
    lint cx = x[i];
    lint cy = y[i];
    p += w.rectangle_freq(cx + 1, INF, cy + 1, INF) + w.rectangle_freq(-INF, cx, -INF, cy);
    q += w.rectangle_freq(-INF, cx, cy + 1, INF) + w.rectangle_freq(cx + 1, INF, -INF, cy);
    r += w.rectangle_freq(-INF, cx, -INF, INF) + w.rectangle_freq(cx + 1, INF, -INF, INF);
    s += w.rectangle_freq(-INF, INF, -INF, cy) + w.rectangle_freq(-INF, INF, cy + 1, INF);
  }
  p /= 2;
  q /= 2;
  r /= 2;
  s /= 2;
  logfixed((p - q) / sqrtl(r * s));
}
0