結果

問題 No.2873 Kendall's Tau
ユーザー Tatsu_mr
提出日時 2024-09-07 13:28:24
言語 C++23
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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