結果
問題 | No.2873 Kendall's Tau |
ユーザー |
![]() |
提出日時 | 2024-09-06 23:21:38 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,074 bytes |
コンパイル時間 | 7,956 ms |
コンパイル使用メモリ | 352,224 KB |
実行使用メモリ | 126,552 KB |
最終ジャッジ日時 | 2024-09-06 23:23:15 |
合計ジャッジ時間 | 70,311 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 WA * 6 |
ソースコード
#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include<bits/stdc++.h>using namespace std;//* ATCODER#include<atcoder/all>using namespace atcoder;typedef modint998244353 mint;//*//* BOOST MULTIPRECISION#include<boost/multiprecision/cpp_int.hpp>using namespace boost::multiprecision;//*/typedef long long ll;#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)template <typename T> bool chmin(T &a, const T &b) {if (a <= b) return false;a = b;return true;}template <typename T> bool chmax(T &a, const T &b) {if (a >= b) return false;a = b;return true;}template <typename T> T max(vector<T> &a){assert(!a.empty());T ret = a[0];for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]);return ret;}template <typename T> T min(vector<T> &a){assert(!a.empty());T ret = a[0];for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]);return ret;}template <typename T> T sum(vector<T> &a){T ret = 0;for (int i=0; i<(int)a.size(); i++) ret += a[i];return ret;}//https://hitonanode.github.io/cplib-cpp/segmenttree/rangetree.hpp.html// CUT begin// 逆元を要求しない領域木template <class S, S (*op)(S, S), S (*e)(), class Coordinate> class rangetree {int n;using Pt = std::pair<Coordinate, Coordinate>;std::vector<Pt> _pts;std::vector<std::vector<Pt>> _range2yxs;std::vector<atcoder::segtree<S, op, e>> segtrees;void _set(int v, Pt p, S val) {auto i = std::distance(_range2yxs[v].begin(),std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{p.second, p.first}));segtrees[v].set(i, val);}void _add(int v, Pt p, S val) {auto i = std::distance(_range2yxs[v].begin(),std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{p.second, p.first}));segtrees[v].set(i, op(segtrees[v].get(i), val));}S _prod(int v, Coordinate yl, Coordinate yr) const {auto comp = [&](const Pt &l, const Pt &r) { return l.first < r.first; };auto il = std::distance(_range2yxs[v].begin(),std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{yl, yl}, comp));auto ir = std::distance(_range2yxs[v].begin(),std::lower_bound(_range2yxs[v].begin(), _range2yxs[v].end(), Pt{yr, yr}, comp));return segtrees[v].prod(il, ir);}public:rangetree() = default;void add_point(Coordinate x, Coordinate y) noexcept { _pts.emplace_back(x, y); }void build() {std::sort(_pts.begin(), _pts.end());_pts.erase(std::unique(_pts.begin(), _pts.end()), _pts.end());n = _pts.size();_range2yxs.resize(n * 2);for (int i = 0; i < n; i++) _range2yxs[n + i] = {{_pts[i].second, _pts[i].first}};for (int i = n - 1; i > 0; i--) {auto &lch = _range2yxs[i * 2];auto &rch = _range2yxs[i * 2 + 1];std::merge(lch.begin(), lch.end(), rch.begin(), rch.end(), std::back_inserter(_range2yxs[i]));_range2yxs[i].erase(std::unique(_range2yxs[i].begin(), _range2yxs[i].end()), _range2yxs[i].end());}for (const auto &v : _range2yxs) segtrees.emplace_back(v.size());}void set(Coordinate x, Coordinate y, S val) {int i = std::distance(_pts.begin(), std::lower_bound(_pts.begin(), _pts.end(), Pt{x, y}));assert(i < n and _pts[i] == std::make_pair(x, y));for (i += n; i; i >>= 1) _set(i, {x, y}, val);}void add(Coordinate x, Coordinate y, S val) {int i = std::distance(_pts.begin(), std::lower_bound(_pts.begin(), _pts.end(), Pt{x, y}));assert(i < n and _pts[i] == std::make_pair(x, y));for (i += n; i; i >>= 1) _add(i, {x, y}, val);}S prod(Coordinate xl, Coordinate xr, Coordinate yl, Coordinate yr) const {auto comp = [](const Pt &l, const Pt &r) { return l.first < r.first; };int l = n + std::distance(_pts.begin(),std::lower_bound(_pts.begin(), _pts.end(), Pt{xl, yr}, comp));int r = n + std::distance(_pts.begin(),std::lower_bound(_pts.begin(), _pts.end(), Pt{xr, yr}, comp));S ret = e();while (l < r) {if (l & 1) ret = op(ret, _prod(l++, yl, yr));if (r & 1) ret = op(ret, _prod(--r, yl, yr));l >>= 1, r >>= 1;}return ret;}S get(Coordinate x, Coordinate y) const { return prod(x, x + 1, y, y + 1); }};int op(int a, int b){return a + b;}int e(){return 0;}// defcomptemplate <typename T>vector<T> compress(vector<T> &X) {vector<T> vals = X;sort(vals.begin(), vals.end());vals.erase(unique(vals.begin(), vals.end()), vals.end());return vals;}// -----// importbisecttemplate <typename T>int bisect_left(vector<T> &X, T v){return lower_bound(X.begin(), X.end(), v) - X.begin();}template <typename T>int bisect_right(vector<T> &X, T v){return upper_bound(X.begin(), X.end(), v) - X.begin();}// -----int main(){ios_base::sync_with_stdio(false);cin.tie(NULL);int n; cin >> n;vector<int> x(n), y(n);map<int,int> cntx;map<int,int> cnty;rangetree<int,op,e,int> rt;rep(i,0,n){cin >> x[i] >> y[i];cntx[x[i]]++;cnty[y[i]]++;}ll p=0,q=0,r=0,s=0;vector<int> fx = compress(x);vector<int> fy = compress(y);rep(i,0,n){x[i]=bisect_left(fx,x[i]);y[i]=bisect_left(fy,y[i]);rt.add_point(x[i],y[i]);}rt.build();r=(ll)n*(n-1)/2;s=(ll)n*(n-1)/2;for(auto[_,c]: cntx){r-=(ll)c*(c-1)/2;}for(auto[_,c]: cnty){s-=(ll)c*(c-1)/2;}const int INF=1e9;rep(i,0,n){p+=rt.prod(x[i]+1,INF,y[i]+1,INF);p+=rt.prod(-INF,x[i],-INF,y[i]);q+=rt.prod(-INF,x[i],y[i]+1,INF);q+=rt.prod(x[i]+1,INF,-INF,y[i]);rt.set(x[i],y[i],1);}cout<<fixed<<setprecision(15);cout<<double(p-q)/sqrt(double(r)*double(s))<<'\n';}