結果

問題 No.2873 Kendall's Tau
ユーザー Tatsu_mr
提出日時 2024-09-06 23:28:28
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,538 bytes
コンパイル時間 5,969 ms
コンパイル使用メモリ 325,200 KB
実行使用メモリ 29,780 KB
最終ジャッジ日時 2024-09-06 23:29:05
合計ジャッジ時間 16,006 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 WA * 27
権限があれば一括ダウンロードができます

ソースコード

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>> ps;
    vector<int> ys;
    map<int, lint> mpx, mpy;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        ps.emplace_back(x, y);
        ys.emplace_back(y);
        mpx[x]++;
        mpy[y]++;
    }
    sort(ps.begin(), ps.end());
    Compression cy(ys);
    atcoder::fenwick_tree<lint> fw(cy.size());
    lint p = 0, q = 0, r = 0, s = 0;
    for (int i = 0; i < n; i++) {
        auto [x, y] = ps[i];
        fw.add(cy.idx(y), 1LL);
        if (i > 0 && ps[i - 1].first == x) {
            continue;
        }
        p += fw.sum(0, cy.idx(y));
        q += fw.sum(cy.idx(y) + 1, cy.size());
    }
    r = s = (lint)n * (lint)(n - 1) / 2LL;
    for (auto [key, val] : mpx) {
        r -= val * (val - 1LL) / 2LL;
    }
    for (auto [key, val] : mpy) {
        s -= val * (val - 1LL) / 2LL;
    }
    cout << fixed << setprecision(10);
    cout << ((ld)p - (ld)q) / sqrtl((ld)r * (ld)s) << endl;
}
0