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

提出ソース

結果

問題	No.2873 Kendall's Tau
ユーザー	shobonvip
提出日時	2024-09-06 23:09:36
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	5,986 bytes
コンパイル時間	6,649 ms
コンパイル使用メモリ	336,260 KB
実行使用メモリ	160,492 KB
最終ジャッジ日時	2024-09-06 23:10:54
合計ジャッジ時間	76,288 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	AC	2 ms 6,944 KB
testcase_02	WA	-
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	WA	-
testcase_07	TLE	-
testcase_08	TLE	-
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	TLE	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	AC	551 ms 31,384 KB
testcase_16	AC	553 ms 32,384 KB
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	AC	488 ms 30,876 KB
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	AC	362 ms 22,368 KB
testcase_31	WA	-
testcase_32	WA	-

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

ソースコード

raw source code

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

ll op(ll a, ll b){return a + b;}
ll 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,ll> cntx;
	map<int,ll> cnty;
	rangetree<ll,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(fx,y[i]);
		rt.add_point(x[i],y[i]);
	}
	rt.build();

	r=n*(n-1)/2;
	s=n*(n-1)/2;
	for(auto[_,c]: cntx){
		r-=c*(c-1)/2;
	}
	for(auto[_,c]: cnty){
		s-=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';

}

yukicoder

結果

テストケース

ソースコード