結果
問題 | No.2873 Kendall's Tau |
ユーザー | テナガザル |
提出日時 | 2024-09-06 23:16:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 755 ms / 4,500 ms |
コード長 | 2,802 bytes |
コンパイル時間 | 1,703 ms |
コンパイル使用メモリ | 137,408 KB |
実行使用メモリ | 14,856 KB |
最終ジャッジ日時 | 2024-09-06 23:17:32 |
合計ジャッジ時間 | 12,912 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <iostream> #include <vector> #include <map> #include <cmath> #include <algorithm> using namespace std; template <typename T> class segTree { private: const T e; int num; std::vector<T> dat; T (*const eval)(T &, T &) {}; public: segTree(std::vector<T> &v, T E, T (*func)(T &, T &)) : e(E), eval(func) { int siz = static_cast<int>(v.size()); for (num = 1; num < siz; num <<= 1); dat = std::vector<T> (2 * num - 1, e); for (int i = 0; i < siz; ++i) dat[i + num - 1] = v[i]; for (int i = num - 2; i >= 0; --i) dat[i] = eval(dat[i * 2 + 1], dat[i * 2 + 2]); } segTree(int n, T E, T (*func)(T &, T &)) : e(E), eval(func) { for (num = 1; num < n; num <<= 1); dat = std::vector<T> (2 * num - 1, e); } void update_a(int i, T val) { for (i += num - 1, dat[i] = val; i != 0;) { i = (i - 1) / 2; dat[i] = eval(dat[i * 2 + 1], dat[i * 2 + 2]); } } void update_r(int i, T val) { for (i += num - 1, dat[i] = eval(dat[i], val); i != 0;) { i = (i - 1) / 2; dat[i] = eval(dat[i * 2 + 1], dat[i * 2 + 2]); } } T getval(int left, int right) { left = max(0, left), right = min(num, right); T ansl = e, ansr = e; for (left += num - 1, right += num - 1; left < right; left >>= 1, right >>= 1) { if (!(left & 1)) ansl = eval(ansl, dat[left]); if (--right & 1) ansr = eval(dat[right], ansr); } return eval(ansl, ansr); } T getval(int id) {return dat[num - 1 + id];} }; int main() { int n; cin >> n; vector<int> x(n), y(n); for (int i = 0; i < n; ++i) cin >> x[i] >> y[i]; auto cal = [&](vector<int> &a) -> long long { long long ret = 0; map<int, int> mp; for (int i = 0; i < n; ++i) ++mp[a[i]]; for (int i = 0; i < n; ++i) ret += n - mp[a[i]]; return ret / 2; }; long long r = cal(x), s = cal(y); vector<pair<int, int>> xy(n); auto cal2 = [&]() -> long long { vector<int> all; for (auto [a, b] : xy) all.push_back(b); sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); int siz = all.size(); segTree<int> sg(siz, 0, [](int &a, int &b) -> int {return a + b;}); long long ret = 0; for (auto [a, b] : xy) { int id = lower_bound(all.begin(), all.end(), b) - all.begin(); ret += sg.getval(0, id); sg.update_r(id, 1); } return ret; }; for (int i = 0; i < n; ++i) xy[i] = {x[i], -y[i]}; sort(xy.begin(), xy.end()); for (int i = 0; i < n; ++i) xy[i].second *= -1; long long p = cal2(); for (int i = 0; i < n; ++i) xy[i] = {-x[i], -y[i]}; sort(xy.begin(), xy.end()); for (int i = 0; i < n; ++i) xy[i].second *= -1; long long q = cal2(); double ans = (p - q) / sqrt((double)r * (double)s); printf("%.10f\n", ans); }