結果
問題 | No.789 範囲の合計 |
ユーザー | むらため |
提出日時 | 2019-02-11 05:21:55 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 111 ms / 1,000 ms |
コード長 | 1,699 bytes |
コンパイル時間 | 2,702 ms |
コンパイル使用メモリ | 62,440 KB |
実行使用メモリ | 13,952 KB |
最終ジャッジ日時 | 2024-07-01 19:20:59 |
合計ジャッジ時間 | 4,389 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 96 ms
10,752 KB |
testcase_03 | AC | 64 ms
8,576 KB |
testcase_04 | AC | 91 ms
11,008 KB |
testcase_05 | AC | 73 ms
10,880 KB |
testcase_06 | AC | 78 ms
10,752 KB |
testcase_07 | AC | 53 ms
8,576 KB |
testcase_08 | AC | 66 ms
9,344 KB |
testcase_09 | AC | 60 ms
9,216 KB |
testcase_10 | AC | 111 ms
13,952 KB |
testcase_11 | AC | 81 ms
11,008 KB |
testcase_12 | AC | 82 ms
11,008 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,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