結果

問題 No.742 にゃんにゃんにゃん 猫の挨拶
ユーザー AEnAEn
提出日時 2022-06-18 00:54:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 89 ms / 2,500 ms
コード長 1,195 bytes
コンパイル時間 337 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 77,188 KB
最終ジャッジ日時 2024-10-09 11:29:34
合計ジャッジ時間 1,977 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

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

# data1n2LSB
class Binary_Indexed_Tree:
def __init__(self, n) -> None:
self._n = n
self.data = [0] * (n+1)
self.depth = n.bit_length()
# alarlxr+1-x
# aiisum
def add(self, p, x) -> None:
"""ai←ai+x O(logn)"""
# pindex0n-1
assert 0 <= p < self._n
# 1-indexed
p += 1
while p <= self._n:
#
self.data[p-1] += x
# LSB
p += p & (-p)
# [l, r)
def sum(self, l, r) -> int:
assert 0 <= l <= r <= self._n
return self._sum(r) - self._sum(l)
def _sum(self, d) -> int:
sm = 0
while d > 0:
sm += self.data[d-1]
# LSB
d -= d & (-d)
return sm
N = int(input())
BIT = Binary_Indexed_Tree(N+1)
M = [int(input()) for _ in range(N)]
M = M[::-1]
res = 0
for num in M:
BIT.add(num, 1)
res += BIT._sum(num)
print(res)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0