結果

問題 No.2873 Kendall's Tau
ユーザー shobonvipshobonvip
提出日時 2024-09-06 23:35:48
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3,013 ms / 4,500 ms
コード長 6,041 bytes
コンパイル時間 8,043 ms
コンパイル使用メモリ 352,532 KB
実行使用メモリ 124,856 KB
最終ジャッジ日時 2024-09-19 15:10:43
合計ジャッジ時間 51,711 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 2,752 ms
119,280 KB
testcase_08 AC 2,850 ms
123,736 KB
testcase_09 AC 2,845 ms
119,316 KB
testcase_10 AC 2,889 ms
124,856 KB
testcase_11 AC 2,984 ms
119,172 KB
testcase_12 AC 3,013 ms
119,872 KB
testcase_13 AC 702 ms
39,184 KB
testcase_14 AC 2,232 ms
105,392 KB
testcase_15 AC 329 ms
25,800 KB
testcase_16 AC 325 ms
25,856 KB
testcase_17 AC 2,061 ms
96,976 KB
testcase_18 AC 1,397 ms
67,664 KB
testcase_19 AC 2,005 ms
94,936 KB
testcase_20 AC 310 ms
26,232 KB
testcase_21 AC 1,621 ms
72,716 KB
testcase_22 AC 517 ms
33,656 KB
testcase_23 AC 1,473 ms
73,612 KB
testcase_24 AC 126 ms
13,616 KB
testcase_25 AC 302 ms
24,736 KB
testcase_26 AC 1,984 ms
96,436 KB
testcase_27 AC 1,000 ms
57,796 KB
testcase_28 AC 2,434 ms
107,076 KB
testcase_29 AC 2,550 ms
111,644 KB
testcase_30 AC 222 ms
18,124 KB
testcase_31 AC 460 ms
32,068 KB
testcase_32 AC 1,539 ms
72,640 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;}

// defcomp
template <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;
}
// -----

// importbisect
template <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){
		rt.add(x[i],y[i],1);
	}
	rep(i,0,n){
		p+=rt.prod(x[i]+1,INF,y[i]+1,INF);
		q+=rt.prod(x[i]+1,INF,-INF,y[i]);
	}
	cout<<fixed<<setprecision(15);
	cout<<(long double)(p-q)/sqrtl((long double)(r)*(long double)(s))<<'\n';

}
0