結果

問題 No.1604 Swap Sort:ONE
コンテスト
ユーザー kokatsu
提出日時 2022-12-06 22:20:25
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,497 bytes
コンパイル時間 2,357 ms
コンパイル使用メモリ 209,456 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-22 17:00:02
合計ジャッジ時間 2,868 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std;

void main() {
    int N;
    readf("%d\n", N);

    auto P = readln.chomp.split.to!(int[]);

    auto ft = new FenwickTree!int(N);
    int res;
    foreach (i, p; P) {
        res += i - ft.sum(p);
        ft.add(p, 1);
    }

    res.writeln;
}

struct FenwickTree(T)
if (isIntegral!T) {

    /// Constructor
    this(U)(U n)
    if (isIntegral!U) {
        size = n.to!T + 1;
        data.length = size;
    }

    /// Adds val to data[idx].
    void add(U)(U idx, T val)
    if (isIntegral!U)
    in (0 < idx && idx < size) {
        U i = idx;
        while (i < size) {
            data[i] += val;
            i += i & -i;
        }
    }

    /// Returns sum(data[1], ..., data[idx]).
    T sum(U)(U idx)
    if (isIntegral!U)
    in (0 <= idx && idx < size) {
        if (idx == 0) {
            return 0;
        }

        T res;
        U i = idx;
        while (i > 0) {
            res += data[i];
            i -= i & -i;
        }
        return res;
    }

    /// Returns the smallest pos that satisfies sum(_tree[1], ..., _tree[pos]) >= x.
    U lowerBound(U = T)(T x) {
        import core.bitop : bsr;

        if (x <= 0) {
            return 0;
        }

        U pos, i = 1 << size.bsr;
        while (i > 0) {
            U t = pos + i;
            if (t < size && data[t] < x) {
                pos = t;
                x -= data[t];
            }
            i >>= 1;
        }
        ++pos;

        return pos;
    }

private:
    T size;
    T[] data;
}
0