結果

問題 No.2873 Kendall's Tau
ユーザー tomeruntomerun
提出日時 2024-09-06 21:53:30
言語 Crystal
(1.11.2)
結果
AC  
実行時間 324 ms / 4,500 ms
コード長 1,416 bytes
コンパイル時間 17,750 ms
コンパイル使用メモリ 341,256 KB
実行使用メモリ 31,732 KB
最終ジャッジ日時 2024-09-06 21:54:19
合計ジャッジ時間 23,674 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 3 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 318 ms
31,680 KB
testcase_08 AC 323 ms
31,644 KB
testcase_09 AC 291 ms
31,676 KB
testcase_10 AC 324 ms
31,732 KB
testcase_11 AC 317 ms
31,592 KB
testcase_12 AC 321 ms
30,952 KB
testcase_13 AC 85 ms
12,340 KB
testcase_14 AC 259 ms
27,900 KB
testcase_15 AC 49 ms
9,600 KB
testcase_16 AC 48 ms
9,728 KB
testcase_17 AC 232 ms
27,040 KB
testcase_18 AC 163 ms
20,516 KB
testcase_19 AC 212 ms
26,180 KB
testcase_20 AC 48 ms
9,856 KB
testcase_21 AC 168 ms
21,528 KB
testcase_22 AC 71 ms
11,276 KB
testcase_23 AC 169 ms
21,700 KB
testcase_24 AC 23 ms
6,944 KB
testcase_25 AC 45 ms
8,192 KB
testcase_26 AC 223 ms
26,852 KB
testcase_27 AC 127 ms
18,392 KB
testcase_28 AC 259 ms
29,004 KB
testcase_29 AC 272 ms
29,056 KB
testcase_30 AC 33 ms
7,296 KB
testcase_31 AC 65 ms
11,136 KB
testcase_32 AC 169 ms
21,780 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = read_line.to_i
xys = Array.new(n) { read_line.split.map(&.to_i) }
xs = xys.map { |v| v[0] }.uniq.sort
ys = xys.map { |v| v[1] }.uniq.sort
cols = Array.new(n) { [] of Int32 }
rows = Array.new(n, 0)
xys.each do |a|
  x, y = a
  xi = xs.bsearch_index { |v| v >= x }.not_nil!
  yi = ys.bsearch_index { |v| v >= y }.not_nil!
  cols[xi] << yi + 1
  rows[yi] += 1
end
r = n.to_i64 * (n - 1) // 2
s = n.to_i64 * (n - 1) // 2
p = 0i64
q = 0i64
bit = BIT(Int32).new(n + 1)
cnt = 0i64
n.times do |x|
  cols[x].each do |y|
    p += bit.cumulative_sum(y - 1)
    q += cnt - bit.cumulative_sum(y)
  end
  cols[x].each do |y|
    bit.add(y, 1)
  end
  r -= cols[x].size.to_i64 * (cols[x].size - 1) // 2
  cnt += cols[x].size
  s -= rows[x].to_i64 * (rows[x] - 1) // 2
end
printf("%.9f\n", (p - q) / r ** 0.5 / s ** 0.5)

class BIT(T)
  # 1-indexed

  def initialize(size : Int)
    len = 1
    while len < size
      len *= 2
    end
    @v = Array(T).new(len + 1, T.zero)
  end

  def cumulative_sum(index : Int)
    ret = T.zero
    while index > 0
      ret += @v[index]
      index &= index - 1
    end
    ret
  end

  def sum(l : Int, r : Int)
    cumulative_sum(r) - cumulative_sum(l - 1)
  end

  def add(index : Int, val : T)
    while index < @v.size
      @v[index] += val
      index += (index & -index)
    end
  end

  def set(index : Int, val : T)
    old = sum(index, index)
    add(index, val - old)
  end
end
0