#1007986 (C++23) No.2873 Kendall's Tau

提出ソース

結果

問題	No.2873 Kendall's Tau
ユーザー	shobonvip
提出日時	2024-09-06 23:35:24
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	6,041 bytes
コンパイル時間	8,548 ms
コンパイル使用メモリ	352,696 KB
実行使用メモリ	125,492 KB
最終ジャッジ日時	2024-09-06 23:37:04
合計ジャッジ時間	56,133 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	3,329 ms 119,972 KB
testcase_08	AC	3,347 ms 124,880 KB
testcase_09	AC	3,370 ms 120,992 KB
testcase_10	AC	3,452 ms 125,492 KB
testcase_11	AC	3,319 ms 119,800 KB
testcase_12	AC	3,326 ms 120,880 KB
testcase_13	AC	776 ms 39,040 KB
testcase_14	AC	2,460 ms 106,348 KB
testcase_15	AC	364 ms 25,800 KB
testcase_16	AC	368 ms 26,176 KB
testcase_17	AC	2,216 ms 97,704 KB
testcase_18	AC	1,584 ms 68,852 KB
testcase_19	AC	2,235 ms 95,176 KB
testcase_20	AC	339 ms 27,136 KB
testcase_21	WA	-
testcase_22	AC	586 ms 34,032 KB
testcase_23	AC	1,660 ms 73,684 KB
testcase_24	WA	-
testcase_25	AC	341 ms 25,248 KB
testcase_26	WA	-
testcase_27	AC	1,189 ms 59,556 KB
testcase_28	AC	2,626 ms 108,724 KB
testcase_29	AC	2,876 ms 112,608 KB
testcase_30	AC	262 ms 18,128 KB
testcase_31	WA	-
testcase_32	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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.set(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';

}

yukicoder

結果

テストケース

ソースコード