結果

問題 No.2873 Kendall's Tau
ユーザー karinohito
提出日時 2024-09-06 22:00:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,036 ms / 4,500 ms
コード長 1,361 bytes
コンパイル時間 2,547 ms
コンパイル使用メモリ 216,952 KB
最終ジャッジ日時 2025-02-24 04:20:57
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/segtree>
using namespace atcoder;
using namespace std;
using ll=long long;

ll op(ll a,ll b){
    return a+b;
}
ll e(){
    return 0;
}

int main() {
    ll N;
    cin>>N;
    vector<pair<ll,ll>> P(N);
    map<ll,ll> M;
    for(int i=0;i<N;i++){
        cin>>P[i].first>>P[i].second;
        M[P[i].first]=M[P[i].second]=1;
    }
    int cnt=0;
    for(auto m:M)M[m.first]=cnt,cnt++;
    for(int i=0;i<N;i++){
        P[i]={M[P[i].first],M[P[i].second]};
    }
    ll D=0;
    vector<ll> U(2,N*(N-1)/2);
    for(int t=0;t<2;t++){
        segtree<ll,op,e> seg(cnt);
        queue<int> Q;
        int x=-1;
        sort(P.begin(),P.end());
        for(int i=0;i<N;i++){
            if(P[i].first!=x){
                ll s=Q.size();
                U[t]-=s*(s-1)/2;
                while(!Q.empty()){
                    int p=Q.front();
                    Q.pop();
                    seg.set(p,seg.get(p)+1);
                }
            }
            x=P[i].first;
            Q.push(P[i].second);
            if(t==0)D+=seg.prod(0,P[i].second);
            else D-=seg.prod(P[i].second+1,cnt);
        }
        ll s=Q.size();
        U[t]-=s*(s-1)/2;
        for(int i=0;i<N;i++)swap(P[i].first,P[i].second);
    }
    cout<<fixed<<setprecision(14);
    cout<<double(D)/double(sqrt(U[0])*sqrt(U[1]))<<endl;
    



}
0