結果
問題 |
No.742 にゃんにゃんにゃん 猫の挨拶
|
ユーザー |
|
提出日時 | 2021-12-12 21:47:31 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 175 ms / 2,500 ms |
コード長 | 1,084 bytes |
コンパイル時間 | 310 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 12,160 KB |
最終ジャッジ日時 | 2024-07-21 09:58:38 |
合計ジャッジ時間 | 1,720 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#BIT class BinaryIndexedTree(): def __init__(self, n): self.n = 1 << (n.bit_length()) self.BIT = [0] * (self.n + 1) def build(self, init_lis): for i, v in enumerate(init_lis): self.add(i, v) def add(self, i, x): i += 1 while i <= self.n: self.BIT[i] += x i += i & -i def sum(self, l, r): return self._sum(r) - self._sum(l) def _sum(self, i): res = 0 while i > 0: res += self.BIT[i] i -= i & -i return res def binary_search(self, x): i = self.n while True: if i & 1: if x > self.BIT[i]: i += 1 break if x > self.BIT[i]: x -= self.BIT[i] i += (i & -i) >> 1 else: i -= (i & -i) >> 1 return i n = int(input()) a = [int(input()) for _ in range(n)] BIT = BinaryIndexedTree(n) ans = 0 for i in range(n): ans += i - BIT._sum(a[i]) BIT.add(a[i], 1) print(ans)