結果

問題 No.694 square1001 and Permutation 3
ユーザー 👑 obakyan
提出日時 2021-05-04 22:04:02
言語 Lua
(LuaJit 2.1.1734355927)
結果
AC  
実行時間 693 ms / 3,000 ms
コード長 1,385 bytes
コンパイル時間 221 ms
コンパイル使用メモリ 5,504 KB
実行使用メモリ 31,560 KB
最終ジャッジ日時 2024-07-23 17:21:50
合計ジャッジ時間 5,374 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

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 c = 0
local a = {}
local amap = {}
for i = 1, n do
  a[i] = io.read("*n")
  amap[a[i]] = true
end
local auniq = {}
for k, _u in pairs(amap) do table.insert(auniq, k) end
table.sort(auniq)
local an = #auniq
for i = 1, an do
  amap[auniq[i]] = i
end
for i = 1, n do
  a[i] = amap[a[i]]
end

local fw = FenwickTree.new(an)
for i = 1, n do
  c = c + fw:sum(a[i])
  fw:add(a[i], 1)
end
c = mfl(n * (n - 1) / 2) - c
print(c)
local acnt = {}
for i = 1, an do acnt[i] = 0 end
for i = 1, n do
  local ai = a[i]
  acnt[ai] = acnt[ai] + 1
end
for i = 2, an do
  acnt[i] = acnt[i] + acnt[i - 1]
end

for i = 1, n - 1 do
  local ai = a[i]
  local largecnt = n - acnt[ai]
  local smallcnt = 1 < ai and acnt[ai - 1] or 0
  c = c + largecnt - smallcnt
  print(c)
end
0