結果
問題 | No.2873 Kendall's Tau |
ユーザー |
![]() |
提出日時 | 2024-09-06 21:40:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,217 bytes |
コンパイル時間 | 4,883 ms |
コンパイル使用メモリ | 267,612 KB |
最終ジャッジ日時 | 2025-02-24 04:08:07 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 WA * 17 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using mint = modint998244353;using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 1000000000000000001long long get(vector<long long> x,vector<long long> y){vector<long long> t = y;sort(t.begin(),t.end());t.erase(unique(t.begin(),t.end()),t.end());vector<pair<long long,long long>> p;rep(i,x.size()){p.emplace_back(x[i],lower_bound(t.begin(),t.end(),y[i])-t.begin());}sort(p.begin(),p.end());fenwick_tree<long long> fw(t.size());long long ret = 0;rep(i,p.size()){ret += fw.sum(p[i].second+1,t.size());fw.add(p[i].second,1);}return ret;}long long g2(vector<long long> x){long long n = x.size();long long ret = n*(n-1)/2;map<long long,long long> mp;rep(i,n){ret -= mp[x[i]];mp[x[i]]++;}return ret;}int main(){int n;cin>>n;vector<long long> x(n),y(n);rep(i,n){cin>>x[i]>>y[i];}long long P = get(x,y);rep(i,n){x[i] *= -1;}long long Q = get(x,y);long long R = g2(x),S = g2(y);long double ans = P-Q;ans /= sqrtl(R*S);ans *= -1;cout<<fixed<<setprecision(15)<<ans<<endl;return 0;}