結果
問題 | No.778 クリスマスツリー |
ユーザー |
![]() |
提出日時 | 2018-12-31 14:37:43 |
言語 | Nim (2.2.0) |
結果 |
AC
|
実行時間 | 97 ms / 2,000 ms |
コード長 | 779 bytes |
コンパイル時間 | 5,454 ms |
コンパイル使用メモリ | 65,960 KB |
実行使用メモリ | 43,032 KB |
最終ジャッジ日時 | 2024-10-14 01:55:05 |
合計ジャッジ時間 | 4,509 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
import sequtils,strutilstypebinaryIndexTree[I:static[int]] = array[I + 1,int]proc add(BIT :var binaryIndexTree,i : int, a : int)=var index = iwhile BIT[0] >= index:BIT[index] += aindex += ((index xor (index - 1)) and index)proc sum(BIT : binaryIndexTree, i : int):int =var index = iwhile index > 0:result += BIT[index]index = (index and (index - 1))varBIT : binaryIndexTree[200010]BIT[0] = 200010varN = stdin.readline.parseIntA = stdin.readline.split.map(parseInt)B = newSeqWith(N + 1,newSeq[int](0))ans = 0for i,a in A:B[a + 1].add(i + 2)proc dfs(i : int) =ans += BIT.sum(i)BIT.add(i, 1)for p in B[i]:dfs(p)BIT.add(i, -1)dfs(1)echo ans