結果
問題 | 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.ceillocal band = bit.bandlocal FenwickTree = {}FenwickTree.create = function(self, n)self.n = nself.v = {}for i = 1, n do self.v[i] = 0 endendFenwickTree.add = function(self, pos, val)while pos <= self.n doself.v[pos] = self.v[pos] + valpos = pos + band(pos, -pos)endendFenwickTree.sum = function(self, r)local ret = 0while 0 < r doret = ret + self.v[r]r = r - band(r, -r)endreturn retendFenwickTree.new = function(n)local obj = {}setmetatable(obj, {__index = FenwickTree})obj:create(n)return objendlocal n = io.read("*n")local c = 0local a = {}local amap = {}for i = 1, n doa[i] = io.read("*n")amap[a[i]] = trueendlocal auniq = {}for k, _u in pairs(amap) do table.insert(auniq, k) endtable.sort(auniq)local an = #auniqfor i = 1, an doamap[auniq[i]] = iendfor i = 1, n doa[i] = amap[a[i]]endlocal fw = FenwickTree.new(an)for i = 1, n doc = c + fw:sum(a[i])fw:add(a[i], 1)endc = mfl(n * (n - 1) / 2) - cprint(c)local acnt = {}for i = 1, an do acnt[i] = 0 endfor i = 1, n dolocal ai = a[i]acnt[ai] = acnt[ai] + 1endfor i = 2, an doacnt[i] = acnt[i] + acnt[i - 1]endfor i = 1, n - 1 dolocal ai = a[i]local largecnt = n - acnt[ai]local smallcnt = 1 < ai and acnt[ai - 1] or 0c = c + largecnt - smallcntprint(c)end