結果

問題 No.2873 Kendall's Tau
ユーザー shobonvipshobonvip
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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){
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';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0