結果

問題 No.778 クリスマスツリー
ユーザー 6soukiti29
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sequtils,strutils
type
binaryIndexTree[I:static[int]] = array[I + 1,int]
proc add(BIT :var binaryIndexTree,i : int, a : int)=
var index = i
while BIT[0] >= index:
BIT[index] += a
index += ((index xor (index - 1)) and index)
proc sum(BIT : binaryIndexTree, i : int):int =
var index = i
while index > 0:
result += BIT[index]
index = (index and (index - 1))
var
BIT : binaryIndexTree[200010]
BIT[0] = 200010
var
N = stdin.readline.parseInt
A = stdin.readline.split.map(parseInt)
B = newSeqWith(N + 1,newSeq[int](0))
ans = 0
for 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
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0