結果

問題 No.694 square1001 and Permutation 3
ユーザー 👑 obakyanobakyan
提出日時 2021-05-04 21:54:41
言語 Lua
(LuaJit 2.1.1696795921)
結果
RE  
実行時間 -
コード長 903 bytes
コンパイル時間 386 ms
コンパイル使用メモリ 7,068 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-07-23 17:13:36
合計ジャッジ時間 4,094 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 WA -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 WA -
testcase_08 WA -
testcase_09 RE -
testcase_10 WA -
testcase_11 RE -
testcase_12 RE -
testcase_13 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

local mfl, mce = math.floor, math.ceil
local band = bit.band
local FenwickTree = {}
FenwickTree.create = function(self, n)
  self.n = n
  self.v = {}
  for i = 1, n do self.v[i] = 0 end
end
FenwickTree.add = function(self, pos, val)
  while pos <= self.n do
    self.v[pos] = self.v[pos] + val
    pos = pos + band(pos, -pos)
  end
end
FenwickTree.sum = function(self, r)
  local ret = 0
  while 0 < r do
    ret = ret + self.v[r]
    r = r - band(r, -r)
  end
  return ret
end
FenwickTree.new = function(n)
  local obj = {}
  setmetatable(obj, {__index = FenwickTree})
  obj:create(n)
  return obj
end

local n = io.read("*n")
local fw = FenwickTree.new(n)
local c = 0
local a = {}
for i = 1, n do
  a[i] = io.read("*n")
  if 1 < a[i] then
    c = c + fw:sum(a[i] - 1)
  end
  fw:add(a[i], 1)
end
c = mfl(n * (n - 1) / 2) - c
print(c)
for i = 1, n - 1 do
  c = c + n - a[i] - (a[i] - 1)
  print(c)
end
0