結果

問題 No.1300 Sum of Inversions
ユーザー AEn
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

class Binary_Indexed_Tree:
def __init__(self, n) -> None:
self._n = n
self.data = [0] * (n+1)
self.depth = n.bit_length()
def add(self, p, x) -> None:
"""ai←ai+x O(logn)"""
assert 0 <= p < self._n
p += 1
while p <= self._n:
self.data[p-1] += x
p += p & (-p)
def sum(self, l, r) -> int:
"""[l,r)"""
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]
d -= d & (-d)
return sm
N = int(input())
A = list(map(int,input().split()))
z = {num:i for i, num in enumerate(list(sorted(set(A))))}
n1 = [0]*N
n2 = [0]*N
sm1 = [0]*N
sm2 = [0]*N
BIT1 = 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 = 0
mod = 998244353
for 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 %= mod
print(res)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0