結果
問題 | No.2873 Kendall's Tau |
ユーザー |
|
提出日時 | 2024-09-07 17:48:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 126 ms / 4,500 ms |
コード長 | 1,210 bytes |
コンパイル時間 | 4,343 ms |
コンパイル使用メモリ | 260,776 KB |
最終ジャッジ日時 | 2025-02-24 05:09:31 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using ll = long long;int main(){ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;ll P = 0, R = 0, S = 0, cn = 0;vector<pair<int,int>> a(n);vector<int> cy(n);for(int i = 0; i < n; i++){auto &&[x, y] = a[i];cin >> x >> y;cy[i] = y;}sort(a.begin(), a.end());sort(cy.begin(), cy.end());cy.erase(unique(cy.begin(), cy.end()), cy.end());const int m = cy.size();atcoder::fenwick_tree<int> fw(m);vector<int> cnty(m);for(int l = 0, r = 0; l < n; l = r){while(r < n && a[r].first == a[l].first) r++;R += cn * (r - l);for(int i = l; i < r; i++){a[i].second = lower_bound(cy.begin(), cy.end(), a[i].second) - cy.begin();int low = fw.sum(0, a[i].second);int up = cn - cnty[a[i].second] - low;P += low - up;}for(int i = l; i < r; i++){cn++, cnty[a[i].second]++;S += cn - cnty[a[i].second];fw.add(a[i].second, 1);}}cout << fixed << setprecision(15) << P / sqrtl((double)R * S) << '\n';}