結果

問題 No.1300 Sum of Inversions
ユーザー eijiroueijirou
提出日時 2020-11-27 22:12:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,058 ms / 2,000 ms
コード長 1,373 bytes
コンパイル時間 236 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 134,152 KB
最終ジャッジ日時 2024-07-26 13:08:07
合計ジャッジ時間 26,771 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

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

# Reference: https://ikatakos.com/pot/programming_algorithm/data_structure/binary_indexed_tree
# Fenwick Tree
# 0-indexed
class BinaryIndexedTree:
# a is virtual array
# a = [0] * n
def __init__(self, n, mod):
self.size = n
self.data = [0] * (n+1)
self.mod = mod
# return sum(a[0:i] % mod)
def query(self, i):
res = 0
while i > 0:
res += self.data[i]
res %= self.mod
i -= i & -i
return res
# a[i] += x
def add(self, i, x):
i += 1
while i <= self.size:
self.data[i] += x
self.data[i] %= self.mod
i += i & -i
def debug(self):
print([self.query(i+1)-self.query(i) for i in range(self.size)])
mod = 998244353
def main():
n = int(input())
a = list(map(int, input().split()))
b = list(sorted(enumerate(a), key=lambda x: x[1]))
a = [(0, 0)] * n
for i in range(n):
a[b[i][0]] = (i, b[i][1])
s1 = BinaryIndexedTree(n, mod)
cnt1 = BinaryIndexedTree(n, mod)
s2 = BinaryIndexedTree(n, mod)
cnt2 = BinaryIndexedTree(n, mod)
ans = 0
for i, x in a[::-1]:
ans += cnt2.query(i)*x+s2.query(i)
s2.add(i, cnt1.query(i)*x+s1.query(i))
cnt2.add(i, cnt1.query(i))
s1.add(i, x)
cnt1.add(i, 1)
print(ans % mod)
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0