結果
問題 | No.742 にゃんにゃんにゃん 猫の挨拶 |
ユーザー |
![]() |
提出日時 | 2022-03-04 13:22:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 85 ms / 2,500 ms |
コード長 | 1,285 bytes |
コンパイル時間 | 123 ms |
コンパイル使用メモリ | 82,404 KB |
実行使用メモリ | 77,312 KB |
最終ジャッジ日時 | 2024-07-18 10:23:02 |
合計ジャッジ時間 | 1,662 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
class BIT:def __init__(self, n):self.n = nself.bit = [0]*(self.n+1) # 1-indexeddef init(self, init_val):for i, v in enumerate(init_val):self.add(i, v)def add(self, i, x):# i: 0-indexedi += 1 # to 1-indexedwhile i <= self.n:self.bit[i] += xi += (i & -i)def sum(self, i, j):# return sum of [i, j)# i, j: 0-indexedreturn self._sum(j) - self._sum(i)def _sum(self, i):# return sum of [0, i)# i: 0-indexedres = 0while i > 0:res += self.bit[i]i -= i & (-i)return resdef lower_bound(self, x):s = 0pos = 0depth = self.n.bit_length()v = 1 << depthfor i in range(depth, -1, -1):k = pos + vif k <= self.n and s + self.bit[k] < x:s += self.bit[k]pos += vv >>= 1return posdef __str__(self): # for debugarr = [self.sum(i,i+1) for i in range(self.n)]return str(arr)n = int(input())bit = BIT(n+1)ans = 0for i in range(n):m = int(input())m -= 1ans += bit.sum(m, bit.n)bit.add(m, 1)print(ans)