結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー |
👑 |
提出日時 | 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 |
ソースコード
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