結果

問題 No.2873 Kendall's Tau
ユーザー InTheBloomInTheBloom
提出日時 2024-09-06 22:51:33
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 845 ms / 4,500 ms
コード長 7,687 bytes
コンパイル時間 6,288 ms
コンパイル使用メモリ 234,592 KB
実行使用メモリ 19,884 KB
最終ジャッジ日時 2024-09-06 22:53:33
合計ジャッジ時間 18,877 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 834 ms
19,572 KB
testcase_08 AC 825 ms
19,884 KB
testcase_09 AC 830 ms
19,232 KB
testcase_10 AC 845 ms
18,516 KB
testcase_11 AC 828 ms
17,688 KB
testcase_12 AC 835 ms
19,540 KB
testcase_13 AC 239 ms
13,808 KB
testcase_14 AC 631 ms
16,024 KB
testcase_15 AC 130 ms
7,744 KB
testcase_16 AC 137 ms
6,944 KB
testcase_17 AC 604 ms
15,768 KB
testcase_18 AC 435 ms
14,880 KB
testcase_19 AC 594 ms
18,540 KB
testcase_20 AC 140 ms
9,160 KB
testcase_21 AC 506 ms
15,016 KB
testcase_22 AC 202 ms
9,624 KB
testcase_23 AC 484 ms
12,592 KB
testcase_24 AC 62 ms
6,944 KB
testcase_25 AC 123 ms
6,944 KB
testcase_26 AC 610 ms
15,980 KB
testcase_27 AC 365 ms
11,000 KB
testcase_28 AC 652 ms
18,888 KB
testcase_29 AC 778 ms
17,808 KB
testcase_30 AC 94 ms
6,940 KB
testcase_31 AC 184 ms
10,768 KB
testcase_32 AC 467 ms
14,864 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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(y[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;
        }
}
0