結果

問題 No.2873 Kendall's Tau
ユーザー tomerun
提出日時 2024-09-06 21:53:30
言語 Crystal
(1.14.0)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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