結果
問題 | No.789 範囲の合計 |
ユーザー | むらため |
提出日時 | 2019-02-11 05:21:55 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 106 ms / 1,000 ms |
コード長 | 1,699 bytes |
コンパイル時間 | 2,480 ms |
コンパイル使用メモリ | 67,256 KB |
実行使用メモリ | 14,320 KB |
最終ジャッジ日時 | 2023-09-14 11:54:17 |
合計ジャッジ時間 | 4,358 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 95 ms
12,704 KB |
testcase_03 | AC | 59 ms
9,480 KB |
testcase_04 | AC | 89 ms
12,648 KB |
testcase_05 | AC | 72 ms
14,320 KB |
testcase_06 | AC | 77 ms
12,680 KB |
testcase_07 | AC | 48 ms
9,360 KB |
testcase_08 | AC | 64 ms
10,808 KB |
testcase_09 | AC | 59 ms
9,768 KB |
testcase_10 | AC | 106 ms
12,996 KB |
testcase_11 | AC | 80 ms
12,596 KB |
testcase_12 | AC | 81 ms
12,652 KB |
testcase_13 | AC | 1 ms
4,376 KB |
testcase_14 | AC | 2 ms
4,376 KB |
ソースコード
import sequtils,algorithm proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "<stdio.h>" ,discardable.} proc scan(): int = while true: let k = getchar_unlocked() if k < '0': return result = 10 * result + k.ord - '0'.ord template useBinaryIndexedTree() = # 部分和検索 / 更新 O(log(N)) type BinaryIndexedTree[T] = ref object data: seq[T] # 引数以下の部分和(Fenwick Tree) proc initBinaryIndexedTree[T](n:int):BinaryIndexedTree[T] = new(result) result.data = newSeq[T](n) proc len[T](self:BinaryIndexedTree[T]): int = self.data.len() proc update[T](self:var BinaryIndexedTree[T],i:int,val:T) = var i = i while i < self.len(): self.data[i] += val i = i or (i + 1) proc `[]`[T](self:BinaryIndexedTree[T],i:int): T = var i = i while i >= 0: result += self.data[i] i = (i and (i + 1)) - 1 proc `$`[T](self:BinaryIndexedTree[T]): string = result = "[" for i in 0..<self.len.min(100): result &= $(self[i]) & ", " return result[0..result.len()-2] & (if self.len > 100 : " ...]" else: "]") proc deduplicated[T](arr: seq[T]): seq[T] = # require sorted result = @[] for a in arr.sorted(cmp[T]): if result.len > 0 and result[^1] == a : continue result &= a useBinaryIndexedTree() let n = scan() let Q = newSeqWith(n,(q:scan(),x:scan(),y:scan())) var V = newSeq[int]() for q in Q: V &= q.x if q.q == 1: V &= q.y V = V.deduplicated() var bit = initBinaryIndexedTree[int](V.len + 1) var ans = 0 for q in Q: let x = V.lowerBound(q.x) if q.q == 0: bit.update(x,q.y) else: let y = V.lowerBound(q.y) if x == 0: ans += bit[y] else: ans += bit[y] - bit[x-1] echo ans