結果
問題 | No.2873 Kendall's Tau |
ユーザー |
![]() |
提出日時 | 2024-10-15 02:11:12 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 13,580 bytes |
コンパイル時間 | 7,333 ms |
コンパイル使用メモリ | 312,772 KB |
実行使用メモリ | 70,400 KB |
最終ジャッジ日時 | 2024-10-15 02:11:46 |
合計ジャッジ時間 | 32,971 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 WA * 17 |
ソースコード
#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};#pragma endregion#line 2 "data-structure/wavelet-matrix/WaveletMatrixRectangle.hpp"class BitVector {private:unsigned n, cur, p;vector<unsigned> acc, bit;vector<unsigned long long> sum, srsum;public:BitVector() {}BitVector(vector<bool> &b, vector<unsigned> &v) {cur = 0;n = b.size();acc.resize(n / 32 + 2, 0);bit.resize(n / 32 + 2, 0);sum.resize(n + 1, 0);srsum.resize(n + 1, 0);for (int i = 0; i < n; i++) {p = i % 32;if (p == 0) {cur++;acc[cur] = acc[cur - 1];}sum[i + 1] = sum[i] + v[i];if (b[i]) {acc[cur] += int(b[i]);bit[cur - 1] |= (1U << (32 - p - 1));}}}inline void srsum_set(const vector<unsigned> &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 / 32];return acc[k / 32] + __builtin_popcount(bit[k / 32] >> (32 - (k & 31)));}inline unsigned long long rank_sum(unsigned k) {return sum[k];}inline unsigned long long rank_srsum(unsigned k) {return srsum[k];}inline bool access(unsigned k) {return (rank(k + 1) - rank(k)) == 1;}};class WaveletMatrix {private:unsigned n;unsigned bitsize;vector<BitVector> b;vector<BitVector> cnt;vector<unsigned> zero, zero2;vector<int> stInd, prev;vector<unsigned> prev_i;vector<int> px;vector<unsigned> compressed;vector<int> cmp;// prev_i[l,r) の中で値がk未満の個数を返すunsigned rank_less_prev(unsigned l, unsigned r, unsigned k) {unsigned less = 0;for (unsigned i = 0; i < bitsize and l < r; i++) {const unsigned rank1_l = cnt[i].rank(l);const unsigned rank1_r = cnt[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 = zero2[i] + rank1_l;r = zero2[i] + rank1_r;} else {l = rank0_l;r = rank0_r;}}return less;}inline unsigned compress(int x) {return distance(cmp.begin(), lower_bound(cmp.begin(), cmp.end(), x));}public:// コンストラクタWaveletMatrix() {}WaveletMatrix(vector<int> x, vector<int> y) {n = x.size();px.resize(n);vector<tuple<int, int>> v(n);for (int i = 0; i < n; i++) {v[i] = {x[i], y[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]);}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]);tmpc[j] = compressed[j];}b[i] = BitVector(bit, compressed);int cur = 0;for (unsigned j = 0; j < n; j++) {if (!bit[j]) {compressed[cur] = tmpc[j];cur++;}}for (unsigned j = 0; j < n; j++) {if (bit[j]) {compressed[cur] = tmpc[j];cur++;}}}for (unsigned i = 0; i < n; i++) {if (stInd[compressed[i]] == -1) {stInd[compressed[i]] = i;}}}// get v[k]unsigned 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, unsigned 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未満の個数、kの個数、kより大きい個数}を返すvector<unsigned> rank_less_more(unsigned l, unsigned r, unsigned k) {unsigned range = r - l;unsigned less = 0;unsigned more = 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 {more += (rank1_r - rank1_l);l = rank0_l;r = rank0_r;}}unsigned rank = range - more - less;return {less, rank, more};}// v[l,r) の中で値がk未満の総和を返すunsigned long long rank_less_sum(unsigned l, unsigned r, unsigned k) {unsigned 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, unsigned 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-1番目に小さい値を返すunsigned 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個の総和を返すunsigned long long kth_sum(unsigned l, unsigned r, unsigned k) {unsigned 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 += uint64_t(cmp[val]) * uint64_t(k);return res;}// v[l,r) の中で[mink,maxk)に入る値の個数を返すunsigned range_freq(unsigned l, unsigned r, int mink, int maxk) {mink = compress(mink);maxk = compress(maxk);return rank_less(l, r, maxk) - rank_less(l, r, mink);}// v[l,r) の中で[mink,maxk)に入る値の総和を返すunsigned long long range_sum(unsigned l, unsigned r, unsigned mink, unsigned maxk) {mink = compress(mink);maxk = compress(maxk);return rank_less_sum(l, r, maxk) - rank_less_sum(l, r, mink);}// x座標が[l,r) かつy座標が[d,u) に入る点の個数を返すunsigned rectangle_freq(int l, int r, int d, int 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) に入る点の総和を返すunsigned long long rectangle_sum(unsigned l, unsigned r, unsigned d, unsigned 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);}// v[l,r) の中の値の種類数を返すunsigned range_count(unsigned l, unsigned r) {return rank_less_prev(l, r, l + 1);}// v[l,r)の中でvalを超えない最大の値を返すunsigned prev_value(unsigned l, unsigned r, unsigned val) {int num = range_freq(l, r, 0, val);if (num == 0) {return UINT32_MAX;} else {return kth_smallest(l, r, num);}}// v[l,r)の中でval以上の最小の値を返すunsigned next_value(unsigned l, unsigned r, unsigned val) {int num = range_freq(l, r, 0, val);if (num == r - l) {return UINT32_MAX;} else {return kth_smallest(l, r, num + 1);}}};int main() {int INF = 1e9 + 10;cin.tie(0);ios::sync_with_stdio(false);int n;in(n);vector<int> x(n), y(n), o(n);rep(i, n) {in(x[i], y[i]);}WaveletMatrix w(x, y);lint p, q, r, s;p = q = r = s = 0;rep(i, n) {int cx = x[i];int 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));}