結果
問題 | No.1300 Sum of Inversions |
ユーザー |
![]() |
提出日時 | 2022-12-24 02:53:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 762 ms / 2,000 ms |
コード長 | 1,430 bytes |
コンパイル時間 | 438 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 184,668 KB |
最終ジャッジ日時 | 2024-11-18 05:06:14 |
合計ジャッジ時間 | 21,738 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
class Binary_Indexed_Tree:def __init__(self, n) -> None:self._n = nself.data = [0] * (n+1)self.depth = n.bit_length()def add(self, p, x) -> None:"""任意の要素ai←ai+xを行う O(logn)"""assert 0 <= p < self._np += 1while p <= self._n:self.data[p-1] += xp += p & (-p)def sum(self, l, r) -> int:"""区間[l,r)で計算"""assert 0 <= l <= r <= self._nreturn self._sum(r) - self._sum(l)def _sum(self, d) -> int:sm = 0while d > 0:sm += self.data[d-1]d -= d & (-d)return smN = int(input())A = list(map(int,input().split()))z = {num:i for i, num in enumerate(list(sorted(set(A))))}n1 = [0]*Nn2 = [0]*Nsm1 = [0]*Nsm2 = [0]*NBIT1 = Binary_Indexed_Tree(len(z)+5)BIT1_s = Binary_Indexed_Tree(len(z)+5)BIT2 = Binary_Indexed_Tree(len(z)+5)BIT2_s = Binary_Indexed_Tree(len(z)+5)for i in range(N):id1 = z[A[i]]id2 = z[A[-1-i]]n1[i] = BIT1.sum(id1+1,len(z))n2[-1-i] = BIT2._sum(id2)sm1[i] = BIT1_s.sum(id1+1,len(z))sm2[-1-i] = BIT2_s._sum(id2)BIT1.add(id1,1)BIT2.add(id2,1)BIT1_s.add(id1,A[i])BIT2_s.add(id2,A[-1-i])res = 0mod = 998244353for i in range(N):if n1[i]>0 and n2[i]>0:res += A[i]*n1[i]*n2[i]+sm1[i]*n2[i]+sm2[i]*n1[i]res %= modprint(res)