結果
問題 | No.2873 Kendall's Tau |
ユーザー | tottoripaper |
提出日時 | 2024-09-08 23:01:06 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 136 ms / 4,500 ms |
コード長 | 2,017 bytes |
コンパイル時間 | 2,630 ms |
コンパイル使用メモリ | 216,660 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-08 23:01:13 |
合計ジャッジ時間 | 6,810 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>#define fst(t) std::get<0>(t)#define snd(t) std::get<1>(t)using ll = std::int64_t;using P = std::tuple<int, int>;struct FenwickTree{std::vector<int> data;FenwickTree(int n) : data(n + 1) {}void add(int k, int v){k += 1;while(k < data.size()){data[k] += v;k += k & -k;}}int sum(int r){r = std::min<int>(r, data.size() - 1);int res = 0;while(r > 0){res += data[r];r -= r & -r;}return res;}int sum(int l, int r){return sum(r) - sum(l);}int at(int k){return sum(k, k + 1);}};int main(){std::cin.tie(nullptr);std::ios::sync_with_stdio(false);int N;std::cin >> N;std::vector<P> xy(N);for(int i=0;i<N;i++){std::cin >> fst(xy[i]) >> snd(xy[i]);}{std::vector<int> y(N);for(int i=0;i<N;i++){y[i] = snd(xy[i]);}std::sort(std::begin(y), std::end(y));y.erase(std::unique(std::begin(y), std::end(y)), std::end(y));for(int i=0;i<N;i++){snd(xy[i]) = std::lower_bound(std::begin(y), std::end(y), snd(xy[i])) - std::begin(y);}}std::sort(std::begin(xy), std::end(xy));FenwickTree t(N);ll p = 0, q = 0, r = 0, s = 0;for(int i=0,j=0;i<N;i=j){while(j < N && fst(xy[j]) == fst(xy[i])){j += 1;}r += 1ll * (j - i) * i;for(int k=i;k<j;k++){ll np = t.sum(snd(xy[k]) + 1, N);ll nn = t.sum(0, snd(xy[k]));p += nn;q += np;}for(int k=i;k<j;k++){ll np = t.sum(snd(xy[k]) + 1, N);ll nn = t.sum(0, snd(xy[k]));s += np + nn;t.add(snd(xy[k]), 1);}}double res = (1.0 * p - q) / std::sqrt(1.0 * r * s);std::cout << std::setprecision(12) << res << std::endl;}