結果
問題 | No.2873 Kendall's Tau |
ユーザー | hongrock |
提出日時 | 2024-09-06 22:13:23 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,270 bytes |
コンパイル時間 | 2,634 ms |
コンパイル使用メモリ | 217,120 KB |
実行使用メモリ | 40,520 KB |
最終ジャッジ日時 | 2024-09-06 22:13:35 |
合計ジャッジ時間 | 10,211 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | AC | 108 ms
11,008 KB |
testcase_14 | WA | - |
testcase_15 | AC | 50 ms
9,728 KB |
testcase_16 | AC | 55 ms
8,832 KB |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | AC | 50 ms
8,960 KB |
testcase_21 | WA | - |
testcase_22 | AC | 71 ms
10,396 KB |
testcase_23 | WA | - |
testcase_24 | AC | 21 ms
6,944 KB |
testcase_25 | AC | 48 ms
9,212 KB |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | AC | 35 ms
7,040 KB |
testcase_31 | AC | 66 ms
10,088 KB |
testcase_32 | WA | - |
ソースコード
#include<bits/stdc++.h> using namespace std; #define pb emplace_back #define mp make_pair using ll = long long; using pii = pair<int,int>; constexpr int mod = 998244353; constexpr int inf = 0x3f3f3f3f; constexpr int N = 2e5 + 10; int n, m, b[N]; int s[N]; int lowbit(int x){ return x & (-x); } void add(int x, int v){ for(; x<=m; x+=lowbit(x)) s[x] += v; } int sum(int x){ int ret = 0; for(; x>0; x-=lowbit(x)) ret += s[x]; return ret; } int query(int L, int R){ if(L > R) return 0; return sum(R) - sum(L - 1); } void _main(){ unordered_map<int, int> cntx, cnty; map<int, vector<int>> g; cin >> n; ll P = 0, Q = 0, R = 0, S = 0; int x, y; m = 0; for(int i=1; i<=n; ++i){ cin >> x >> y; R += (i - ++cntx[x]); S += (i - ++cnty[y]); g[x].pb(y); b[m++] = y; } sort(b, b+m); m = unique(b, b+m) - b; for(auto &[x, vec] : g){ for(int y : vec){ int j = lower_bound(b, b+m, y) - b + 1; P += query(1, j - 1); Q += query(j + 1, m); } for(int y : vec){ int j = lower_bound(b, b+m, y) - b + 1; add(j, 1); } } cout << setprecision(8) << (P - Q) * 1.0 / sqrt(R * S) << '\n'; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); _main(); return 0; }