結果

問題 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
52,336 KB
testcase_01 AC 38 ms
53,760 KB
testcase_02 AC 38 ms
52,728 KB
testcase_03 AC 807 ms
104,672 KB
testcase_04 AC 785 ms
105,880 KB
testcase_05 AC 641 ms
105,796 KB
testcase_06 AC 914 ms
109,200 KB
testcase_07 AC 876 ms
107,356 KB
testcase_08 AC 966 ms
109,840 KB
testcase_09 AC 952 ms
109,592 KB
testcase_10 AC 526 ms
103,956 KB
testcase_11 AC 525 ms
104,272 KB
testcase_12 AC 777 ms
105,440 KB
testcase_13 AC 751 ms
106,440 KB
testcase_14 AC 1,058 ms
134,152 KB
testcase_15 AC 948 ms
109,964 KB
testcase_16 AC 817 ms
104,140 KB
testcase_17 AC 525 ms
101,384 KB
testcase_18 AC 574 ms
103,384 KB
testcase_19 AC 700 ms
106,844 KB
testcase_20 AC 711 ms
107,040 KB
testcase_21 AC 708 ms
106,636 KB
testcase_22 AC 646 ms
106,092 KB
testcase_23 AC 902 ms
109,304 KB
testcase_24 AC 660 ms
106,028 KB
testcase_25 AC 565 ms
103,920 KB
testcase_26 AC 560 ms
103,776 KB
testcase_27 AC 632 ms
105,920 KB
testcase_28 AC 989 ms
112,184 KB
testcase_29 AC 687 ms
107,260 KB
testcase_30 AC 961 ms
110,352 KB
testcase_31 AC 649 ms
105,900 KB
testcase_32 AC 649 ms
106,076 KB
testcase_33 AC 535 ms
121,684 KB
testcase_34 AC 572 ms
133,788 KB
testcase_35 AC 560 ms
112,276 KB
testcase_36 AC 587 ms
133,436 KB
権限があれば一括ダウンロードができます

ソースコード

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()
0