結果
問題 | No.2873 Kendall's Tau |
ユーザー | lmori |
提出日時 | 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 | - |
ソースコード
#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)); }