結果
問題 | No.742 にゃんにゃんにゃん 猫の挨拶 |
ユーザー |
|
提出日時 | 2021-10-23 16:47:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 94 ms / 2,500 ms |
コード長 | 1,088 bytes |
コンパイル時間 | 404 ms |
コンパイル使用メモリ | 82,252 KB |
実行使用メモリ | 76,640 KB |
最終ジャッジ日時 | 2024-09-25 07:56:40 |
合計ジャッジ時間 | 2,193 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
class BIT:def __init__(self, n):self._n = nself.data = [0]*(n+1)def add(self, p, x): # pは0-indexedassert 0 <= p < self._np += 1while p <= self._n:self.data[p] += xp += p & -pdef sum_range(self, l, r): # l,rは0-indexedで閉区間[l,r]の区間和を求めるassert 0 <= l <= r <= self._nreturn self._sum(r+1)-self._sum(l)def _sum(self, r):s = 0while r > 0:s += self.data[r]r -= r & -rreturn sdef lower_bound(self, x): # a0+a1+...+ai>=xなるiのminを求める(0-indexed)lo = 1hi = self._nret = 1 << 60while lo <= hi:m = (lo+hi)//2if self._sum(m) >= x:ret = min(ret, m)hi = m-1else:lo = m+1return ret-1N = int(input())M = [int(input())-1 for _ in range(N)]B = BIT(N)ans = 0for i in range(N):num = B.sum_range(0, M[i])ans += i-numB.add(M[i], 1)print(ans)