結果
問題 | No.2873 Kendall's Tau |
ユーザー | GOTKAKO |
提出日時 | 2024-09-06 21:55:55 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 459 ms / 4,500 ms |
コード長 | 4,780 bytes |
コンパイル時間 | 2,860 ms |
コンパイル使用メモリ | 226,600 KB |
実行使用メモリ | 29,620 KB |
最終ジャッジ日時 | 2024-09-06 21:56:57 |
合計ジャッジ時間 | 9,995 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 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 | 398 ms
29,528 KB |
testcase_08 | AC | 459 ms
29,516 KB |
testcase_09 | AC | 397 ms
29,620 KB |
testcase_10 | AC | 401 ms
29,556 KB |
testcase_11 | AC | 389 ms
29,408 KB |
testcase_12 | AC | 386 ms
28,408 KB |
testcase_13 | AC | 103 ms
11,624 KB |
testcase_14 | AC | 307 ms
24,732 KB |
testcase_15 | AC | 51 ms
8,440 KB |
testcase_16 | AC | 54 ms
8,716 KB |
testcase_17 | AC | 270 ms
23,904 KB |
testcase_18 | AC | 192 ms
17,600 KB |
testcase_19 | AC | 271 ms
23,156 KB |
testcase_20 | AC | 53 ms
8,584 KB |
testcase_21 | AC | 210 ms
18,748 KB |
testcase_22 | AC | 79 ms
10,376 KB |
testcase_23 | AC | 213 ms
18,856 KB |
testcase_24 | AC | 25 ms
6,944 KB |
testcase_25 | AC | 48 ms
8,172 KB |
testcase_26 | AC | 289 ms
23,956 KB |
testcase_27 | AC | 153 ms
15,548 KB |
testcase_28 | AC | 319 ms
25,740 KB |
testcase_29 | AC | 345 ms
26,748 KB |
testcase_30 | AC | 39 ms
7,168 KB |
testcase_31 | AC | 79 ms
10,232 KB |
testcase_32 | AC | 215 ms
18,968 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using SS = int; class SegmentTree{ public: int siz = 1,n; vector<SS> dat; SS op(SS a, SS b){return a+b;} SS e(){return 0;} void renew (SS &a,SS x){ a = op(a,x); //a = x; //その他. } void make(int N){ while(siz < N) siz *= 2; n = N; dat.resize(siz*2,e()); } void make2(int N,vector<SS> &A){ make(N); for(int i=0; i<N; i++){ int pos = i+siz; dat.at(pos) = A.at(i); } for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1)); } void update(int pos,SS x){ pos = pos+siz; renew(dat.at(pos),x); while(pos != 1){ pos = pos/2; dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1)); } } SS findans(int l, int r){ SS retl = e(),retr = e(); l += siz,r += siz; while(l < r){ if(l&1) retl = op(retl,dat.at(l++)); if(r&1) retr = op(dat.at(--r),retr); l >>= 1; r >>= 1; } return op(retl,retr); } SS get(int pos){return dat.at(pos+siz);} SS rangeans(int l, int r){return findans(l,r);} SS allrange(){return dat.at(1);} //rightは) leftは[で 渡す&返す. int maxright(const function<bool(SS)> f,int l = 0){ l += siz; int r = n+siz; vector<int> ls,rs; while(l < r){ if(l&1) ls.push_back(l++); if(r&1) rs.push_back(--r); l >>= 1; r >>= 1; } SS okl = e(); for(int i=0; i<ls.size(); i++){ l = ls.at(i); SS now = op(okl,dat.at(l)); if(!f(now)){ while(l < siz){ l <<= 1; now = op(okl,dat.at(l)); if(f(now)){okl = now; l++;} } return l-siz; } okl = now; } for(int i=rs.size()-1; i>=0; i--){ l = rs.at(i); SS now = op(okl,dat.at(l)); if(!f(now)){ while(l < siz){ l <<= 1; now = op(okl,dat.at(l)); if(f(now)){okl = now; l++;} } return l-siz; } okl = now; } return n; } int minleft(const function<bool(SS)> f,int r = -1){ if(r == -1) r = n; int l = siz; r += siz; vector<int> ls,rs; while(l < r){ if(l&1) ls.push_back(l++); if(r&1) rs.push_back(--r); l >>= 1; r >>= 1; } SS okr = e(); for(int i=0; i<rs.size(); i++){ r = rs.at(i); SS now = op(dat.at(r),okr); if(!f(now)){ while(r < siz){ r <<= 1; r++; now = op(dat.at(r),okr); if(f(now)){okr = now; r--;} } return r+1-siz; } } for(int i=ls.size()-1; i>=0; i--){ r = ls.at(i); SS now = op(dat.at(r),okr); if(!f(now)){ while(r < siz){ r <<= 1; r++; now = op(dat.at(r),okr); if(f(now)){okr = now; r--;} } return r+1-siz; } } return 0; } //ノーマルセグ木.一年の時を経て漸く二分探索実装した. }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); long long N; cin >> N; vector<pair<int,int>> XY(N); vector<int> all; for(auto &[x,y] : XY) cin >> x >> y,all.push_back(x),all.push_back(y); sort(all.begin(),all.end()); all.erase(unique(all.begin(),all.end()),all.end()); vector<long long> Xs(2*N),Ys(2*N); map<pair<int,int>,long long> XYs; for(auto &[x,y] : XY){ x = lower_bound(all.begin(),all.end(),x)-all.begin(); y = lower_bound(all.begin(),all.end(),y)-all.begin(); Xs.at(x)++; Ys.at(y)++; XYs[{x,y}]++; } long long P = 0,Q = 0,R = 0,S = 0,ex = 0,pairs = N*(N-1)/2; for(auto &[k,v] : XYs) ex += v*(v-1)/2; for(auto &v : Xs) R += v*(v-1)/2; for(auto &v : Ys) S += v*(v-1)/2; sort(XY.begin(),XY.end()); int back = -1; vector<int> memo; SegmentTree Z; Z.make(2*N); for(auto &[x,y] : XY){ if(x != back){ for(auto &p : memo) Z.update(p,1); memo.clear(); } back = x; P += Z.rangeans(0,y); memo.push_back(y); } Q = pairs-P-R-S+ex; R = pairs-R; S = pairs-S; cout << fixed << setprecision(20) << (P-Q+(long double)0.0)/sqrtl((long double)R*S) << endl; }