結果
| 問題 |
No.2873 Kendall's Tau
|
| コンテスト | |
| ユーザー |
 InTheBloom
|
| 提出日時 | 2024-09-06 22:49:01 |
| 言語 | D (dmd 2.109.1) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,684 bytes |
| コンパイル時間 | 3,805 ms |
| コンパイル使用メモリ | 236,436 KB |
| 実行使用メモリ | 21,000 KB |
| 最終ジャッジ日時 | 2024-09-06 22:49:28 |
| 合計ジャッジ時間 | 18,256 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 4 WA * 26 |
ソースコード
import std;
void main () {
int N = readln.chomp.to!int;
auto x = new int[](N);
auto y = new int[](N);
foreach (i; 0..N) readln.read(x[i], y[i]);
// PとQをどう求めるかが最も難しい。
// Pについて考える。
// 面倒なので、片方の大小関係は異なるとして考えたい。
// xj < xiを仮定する。この時、yj < yiが必要十分条件。xの昇順にデータを追加することを考えると、rectangle sumの特殊ケースに帰着する。これは平面走査で解ける。
// Qも不等号の向きを反転させればよい。
long P = () {
long res = 0;
auto index = iota(N).array.sort!((i, j) => x[i] < x[j]).array;
auto rsq = new DynamicSegmentTree!(int, (int a, int b) => a + b, () => 0)(10L ^^ 10);
const int pad = 10 ^^ 9;
int L = 0, R = 0;
while (L < N) {
while (R < N) {
if (x[index[L]] != x[index[R]]) break;
R++;
}
foreach (U; L..R) {
res += rsq.prod(0, y[index[U]] + pad);
}
// 追加
foreach (U; L..R) {
rsq.set(y[index[U]] + pad, rsq.get(y[index[U]] + pad) + 1);
}
L = R;
}
return res;
}();
long Q = () {
long res = 0;
auto index = iota(N).array.sort!((i, j) => x[i] < x[j]).array;
auto rsq = new DynamicSegmentTree!(int, (int a, int b) => a + b, () => 0)(10L ^^ 10);
const int pad = 10 ^^ 9;
int L = 0, R = 0;
while (L < N) {
while (R < N) {
if (x[index[L]] != x[index[R]]) break;
R++;
}
foreach (U; L..R) {
res += rsq.prod(y[index[U]] + pad + 1, 10L ^^ 10);
}
// 追加
foreach (U; L..R) {
rsq.set(y[index[U]] + pad, rsq.get(index[U] + pad) + 1);
}
L = R;
}
return res;
}();
long R = () {
long res = 0;
auto index = iota(N).array.sort!((i, j) => x[i] < x[j]).array;
int L = 0, R = 0;
while (L < N) {
while (R < N) {
if (x[index[L]] != x[index[R]]) break;
R++;
}
res += 1L * (R - L) * (N - (R - L));
L = R;
}
return res / 2;
}();
long S = () {
long res = 0;
auto index = iota(N).array.sort!((i, j) => y[i] < y[j]).array;
int L = 0, R = 0;
while (L < N) {
while (R < N) {
if (y[index[L]] != y[index[R]]) break;
R++;
}
res += 1L * (R - L) * (N - (R - L));
L = R;
}
return res / 2;
}();
double ans = (P - Q) / sqrt(R.to!double) / sqrt(S.to!double);
writefln("%.10f", ans);
}
void read (T...) (string S, ref T args) {
import std.conv : to;
import std.array : split;
auto buf = S.split;
foreach (i, ref arg; args) {
arg = buf[i].to!(typeof(arg));
}
}
import std.traits : ReturnType, isCallable, Parameters;
import std.meta : AliasSeq;
class DynamicSegmentTree (T, alias op, alias e) {
// TODO: assertのメッセージを表示
static assert(isCallable!(op));
static assert(isCallable!(e));
static assert(is (ReturnType!(op) == T));
static assert(is (ReturnType!(e) == T));
static assert(is (Parameters!(op) == AliasSeq!(T, T)));
static assert(is (Parameters!(e) == AliasSeq!()));
// 内部が1-indexedで動的な完全二分セグメント木
import std.format : format;
public:
this (long N_)
in { assert(1 <= N_, format("Dynamic SegmentTree: N = %s does not satisfy constraints. N must be in range of [1, %s]", 4 * 10L^^18)); }
do {
length = N_;
// N_以上の2冪に設定
N = 1;
while (N < N_) N *= 2;
}
void set (long idx, T val)
in { assert(0 <= idx && idx < length, format("Dynamic SegmentTree: idx = %s does not satisfy constraints. idx must be in range of [0, %s)", idx, length)); }
do {
idx++;
internal_set(root, idx, val, 1, N + 1);
}
T get (long idx)
in { assert(0 <= idx && idx < length, format("Dynamic SegmentTree: idx = %s does not satisfy constraints. idx must be in range of [0, %s)", idx, length)); }
do {
idx++;
return internal_get(root, idx, 1, N + 1);
}
T prod (long l, long r)
in {
assert(0 <= l && l < length, format("Dynamic SegmentTree: l = %s does not satisfy constraints. l must be in range of [0, %s)", l, length));
assert(0 <= r && r <= length, format("Dynamic SegmentTree: r = %s does not satisfy constraints. r must be in range of [0, %s]", r, length));
assert(l <= r, format("Dynamic SegmentTree: l = %s, r = %s does not satisfy constraints. l <= r must be satisfied.", l, r));
}
do {
l++, r++;
if (l == r) return e();
return internal_prod(root, l, r, 1, N + 1);
}
T all_prod () {
return internal_prod(root, 1, N + 1, 1, N + 1);
}
private:
struct node {
long index;
T value, product;
node *left = null, right = null;
}
void node_update (node *n) {
n.product = op(
op((n.left == null ? e() : n.left.product), n.value),
(n.right == null ? e() : n.right.product)
);
}
node *root = null;
long N = 0;
long length = 0;
// [l, r) : 今見ている部分木が管理する範囲
node *internal_set (ref node *cur, long idx, T val, long l, long r) {
if (cur == null) {
return cur = new node(idx, val, val, null, null);
}
if (cur.index == idx) {
cur.value = val;
node_update(cur);
return cur;
}
// 既に部分木管理ノードが存在するときの処理
import std.algorithm : swap;
long mid = (l + r) / 2;
if (idx < mid) {
// 今いる人を押しのける
if (cur.index < idx) { swap(cur.value, val); swap(cur.index, idx); }
cur.left = internal_set(cur.left, idx, val, l, mid);
}
else {
if (idx < cur.index) { swap(cur.value, val); swap(cur.index, idx); }
cur.right = internal_set(cur.right, idx, val, mid, r);
}
node_update(cur);
return cur;
}
T internal_get (const node *cur, long idx, long l, long r) {
if (cur == null) return e();
if (cur.index == idx) return cur.value;
long mid = (l + r) / 2;
if (idx < mid) return internal_get(cur.left, idx, l, mid);
return internal_get(cur.right, idx, mid, r);
}
// [a, b) = 要求区間
T internal_prod (const node *cur, long a, long b, long l, long r) {
if (cur == null || b <= l || r <= a) return e();
if (a <= l && r <= b) return cur.product;
long mid = (l + r) / 2;
T res = internal_prod(cur.left, a, b, l, mid);
if (a <= cur.index && cur.index < b) res = op(res, cur.value);
res = op(res, internal_prod(cur.right, a, b, mid, r));
return res;
}
}