結果
問題 | No.789 範囲の合計 |
ユーザー | 👑 obakyan |
提出日時 | 2019-09-17 11:08:39 |
言語 | Lua (LuaJit 2.1.1696795921) |
結果 |
AC
|
実行時間 | 394 ms / 1,000 ms |
コード長 | 2,702 bytes |
コンパイル時間 | 292 ms |
コンパイル使用メモリ | 5,324 KB |
実行使用メモリ | 26,000 KB |
最終ジャッジ日時 | 2023-09-21 16:42:33 |
合計ジャッジ時間 | 5,611 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 341 ms
25,884 KB |
testcase_03 | AC | 189 ms
8,976 KB |
testcase_04 | AC | 304 ms
25,208 KB |
testcase_05 | AC | 326 ms
26,000 KB |
testcase_06 | AC | 340 ms
25,852 KB |
testcase_07 | AC | 156 ms
8,824 KB |
testcase_08 | AC | 222 ms
17,436 KB |
testcase_09 | AC | 211 ms
13,236 KB |
testcase_10 | AC | 394 ms
25,860 KB |
testcase_11 | AC | 306 ms
25,244 KB |
testcase_12 | AC | 307 ms
25,376 KB |
testcase_13 | AC | 1 ms
4,380 KB |
testcase_14 | AC | 1 ms
4,380 KB |
ソースコード
local mfl, mce, mmi = math.floor, math.ceil, math.min local SegTree = {} SegTree.updateAll = function(self) for i = self.stagenum - 1, 1, -1 do for j = 1, self.cnt[i] do self.stage[i][j] = self.stage[i + 1][j * 2 - 1] + self.stage[i + 1][j * 2] end end end SegTree.create = function(self, n) local stagenum, mul = 1, 1 self.cnt, self.stage, self.size = {1}, {{}}, {} while mul < n do mul, stagenum = mul * 2, stagenum + 1 self.cnt[stagenum], self.stage[stagenum] = mul, {} end for i = 1, stagenum do self.size[i] = self.cnt[stagenum + 1 - i] end self.stagenum = stagenum for i = 1, mul do self.stage[stagenum][i] = 0 end self:updateAll() end SegTree.getRange = function(self, left, right) if left == right then return self.stage[self.stagenum][left] end local start_stage = 1 while right - left + 1 < self.size[start_stage] do start_stage = start_stage + 1 end local ret = 0 local t1, t2, t3 = {start_stage}, {left}, {right} while 0 < #t1 do local stage, l, r = t1[#t1], t2[#t1], t3[#t1] table.remove(t1) table.remove(t2) table.remove(t3) local sz = self.size[stage] if (l - 1) % sz ~= 0 then local newr = mmi(r, mce((l - 1) / sz) * sz) table.insert(t1, stage + 1) table.insert(t2, l) table.insert(t3, newr) l = newr + 1 end if sz <= r + 1 - l then ret = ret + self.stage[stage][mce(l / sz)] l = l + sz end if l <= r then table.insert(t1, stage + 1) table.insert(t2, l) table.insert(t3, r) end end return ret end SegTree.addValue = function(self, idx, value, silent) self.stage[self.stagenum][idx] = self.stage[self.stagenum][idx] + value if not silent then for i = self.stagenum - 1, 1, -1 do local dst = mce(idx / 2) local rem = dst * 4 - 1 - idx self.stage[i][dst] = self.stage[i + 1][idx] + self.stage[i + 1][rem] idx = dst end end end SegTree.new = function(n) local obj = {} setmetatable(obj, {__index = SegTree}) obj:create(n) return obj end local n = io.read("*n") local a, b, c = {}, {}, {} local t = {} for i = 1, n do a[i], b[i], c[i] = io.read("*n", "*n", "*n") b[i] = b[i] + 1 table.insert(t, b[i]) if a[i] == 1 then c[i] = c[i] + 1 table.insert(t, c[i]) end end table.sort(t) do local u = {t[1]} for i = 2, #t do if t[i] ~= t[i - 1] then table.insert(u, t[i]) end end t = u end local map = {} for i = 1, #t do map[t[i]] = i end local st = SegTree.new(#t) local ret = 0 for i = 1, n do if a[i] == 0 then local idx = map[b[i]] st:addValue(idx, c[i]) else local i1, i2 = map[b[i]], map[c[i]] ret = ret + st:getRange(i1, i2) end end print(ret)