結果
問題 | No.2873 Kendall's Tau |
ユーザー |
|
提出日時 | 2024-09-06 23:58:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 517 ms / 4,500 ms |
コード長 | 1,670 bytes |
コンパイル時間 | 2,566 ms |
コンパイル使用メモリ | 220,668 KB |
最終ジャッジ日時 | 2025-02-24 05:01:28 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <atcoder/fenwicktree>#include <bits/stdc++.h>using namespace std;using ll = long long;#define rep(i, n) for (int i = 0; i < (int)(n); i++)void solve() {ll n;cin >> n;vector<pair<ll, ll>> xy(n);rep(i, n) cin >> xy[i].first >> xy[i].second;sort(xy.begin(), xy.end());vector<ll> pre(n, -1), nex(n, 1);rep(i, n) {while (xy[pre[i] + 1].first < xy[i].first)pre[i]++;while (nex[i] < n && xy[i].first == xy[nex[i]].first)nex[i]++;if (i < n - 1)pre[i + 1] = pre[i], nex[i + 1] = nex[i];}priority_queue<pair<ll, ll>> que;map<ll, vector<ll>> yis;atcoder::fenwick_tree<ll> ft(n);rep(i, n) {ll y = xy[i].second;que.emplace(y, i);yis[y].push_back(i);}ll p = 0, q = 0, last_y = 1e18;while (!que.empty()) {auto [y, i] = que.top();que.pop();if (y < last_y) {for (const auto j : yis[last_y])ft.add(j, 1);last_y = y;}if (pre[i] >= 0) {q += ft.sum(0, pre[i] + 1);}if (nex[i] <= n - 1) {p += ft.sum(nex[i], n);}}ll r = 0, s = 0;{ll rem = n;map<ll, ll> cnt;rep(i, n) cnt[xy[i].first]++;for (const auto [k, v] : cnt)r += v * (rem - v), rem -= v;}{ll rem = n;map<ll, ll> cnt;rep(i, n) cnt[xy[i].second]++;for (const auto [k, v] : cnt)s += v * (rem - v), rem -= v;}double ans = p - q;ans /= sqrt(double(r) * double(s));cout << fixed << setprecision(16) << ans << '\n';}int main() {std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);int T = 1;for (int t = 0; t < T; t++) {solve();}return 0;}