結果

問題 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
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0