結果

問題 No.2873 Kendall's Tau
ユーザー Tatsu_mrTatsu_mr
提出日時 2024-09-07 13:28:24
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 675 ms / 4,500 ms
コード長 1,697 bytes
コンパイル時間 6,122 ms
コンパイル使用メモリ 325,856 KB
実行使用メモリ 29,612 KB
最終ジャッジ日時 2024-09-07 13:28:41
合計ジャッジ時間 16,642 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,948 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 534 ms
21,788 KB
testcase_08 AC 651 ms
27,944 KB
testcase_09 AC 549 ms
21,876 KB
testcase_10 AC 675 ms
29,612 KB
testcase_11 AC 558 ms
21,664 KB
testcase_12 AC 643 ms
28,024 KB
testcase_13 AC 145 ms
9,636 KB
testcase_14 AC 494 ms
25,424 KB
testcase_15 AC 80 ms
8,112 KB
testcase_16 AC 83 ms
7,296 KB
testcase_17 AC 394 ms
17,532 KB
testcase_18 AC 287 ms
16,864 KB
testcase_19 AC 370 ms
18,020 KB
testcase_20 AC 83 ms
7,836 KB
testcase_21 AC 314 ms
15,764 KB
testcase_22 AC 122 ms
9,708 KB
testcase_23 AC 309 ms
16,248 KB
testcase_24 AC 34 ms
6,940 KB
testcase_25 AC 73 ms
7,388 KB
testcase_26 AC 389 ms
17,120 KB
testcase_27 AC 236 ms
14,288 KB
testcase_28 AC 476 ms
21,932 KB
testcase_29 AC 538 ms
25,000 KB
testcase_30 AC 59 ms
6,940 KB
testcase_31 AC 116 ms
8,260 KB
testcase_32 AC 312 ms
15,840 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;

template <class T>
struct Compression {
    vector<T> a;
    
    Compression(vector<T> a_) : a(a_) {
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
    }
    
    int size() {
        return (int)a.size();
    }
    
    T val(int p) {
        return a[p];
    }
    
    int idx(T x) {
        int res = lower_bound(a.begin(), a.end(), x) - a.begin();
        return res;
    }
};

using lint = long long;
using ld = long double;;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> xy;
    map<int, lint> mpx, mpy;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        xy.emplace_back(x, y);
        mpx[x]++;
        mpy[y]++;
    }
    auto calc = [&]() {
        vector<int> ys(n);
        for (int i = 0; i < n; i++) {
            ys[i] = xy[i].second;
        }
        Compression cy(ys);
        int sz = cy.size();
        atcoder::fenwick_tree<lint> fw(sz);
        lint res = 0;
        for (int i = 0; i < n; i++) {
            auto [x, y] = xy[i];
            res += fw.sum(cy.idx(y) + 1, sz);
            fw.add(cy.idx(y), 1LL);
        }
        return res;
    };
    lint p, q, r, s;
    sort(xy.begin(), xy.end());
    q = calc();
    for (int i = 0; i < n; i++) {
        xy[i].second *= -1;
    }
    sort(xy.begin(), xy.end());
    p = calc();
    r = s = (lint)n * (lint)(n - 1) / 2LL;
    for (auto [a, b] : mpx) {
        r -= b * (b - 1LL) / 2LL;
    }
    for (auto [a, b] : mpy) {
        s -= b * (b - 1LL) / 2LL;
    }
    cout << fixed << setprecision(10) << (ld)(p - q) / (sqrt((ld)r) * sqrt((ld)s)) << endl;
}
0