結果

問題 No.1300 Sum of Inversions
ユーザー eijiroueijirou
提出日時 2020-11-27 22:12:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,075 ms / 2,000 ms
コード長 1,373 bytes
コンパイル時間 363 ms
コンパイル使用メモリ 87,172 KB
実行使用メモリ 136,696 KB
最終ジャッジ日時 2023-10-01 06:19:22
合計ジャッジ時間 29,337 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 75 ms
71,388 KB
testcase_01 AC 75 ms
71,504 KB
testcase_02 AC 74 ms
71,036 KB
testcase_03 AC 831 ms
106,512 KB
testcase_04 AC 818 ms
106,392 KB
testcase_05 AC 670 ms
101,328 KB
testcase_06 AC 951 ms
129,112 KB
testcase_07 AC 931 ms
108,976 KB
testcase_08 AC 1,016 ms
129,944 KB
testcase_09 AC 1,013 ms
129,976 KB
testcase_10 AC 577 ms
102,880 KB
testcase_11 AC 593 ms
102,868 KB
testcase_12 AC 852 ms
106,088 KB
testcase_13 AC 783 ms
105,740 KB
testcase_14 AC 1,075 ms
135,956 KB
testcase_15 AC 968 ms
129,976 KB
testcase_16 AC 820 ms
107,268 KB
testcase_17 AC 530 ms
100,540 KB
testcase_18 AC 589 ms
101,804 KB
testcase_19 AC 710 ms
101,204 KB
testcase_20 AC 762 ms
102,024 KB
testcase_21 AC 724 ms
102,280 KB
testcase_22 AC 637 ms
101,316 KB
testcase_23 AC 921 ms
128,800 KB
testcase_24 AC 658 ms
100,744 KB
testcase_25 AC 570 ms
102,772 KB
testcase_26 AC 558 ms
102,792 KB
testcase_27 AC 628 ms
102,072 KB
testcase_28 AC 1,009 ms
134,336 KB
testcase_29 AC 711 ms
101,908 KB
testcase_30 AC 1,049 ms
130,020 KB
testcase_31 AC 706 ms
101,088 KB
testcase_32 AC 721 ms
100,028 KB
testcase_33 AC 566 ms
115,172 KB
testcase_34 AC 586 ms
136,696 KB
testcase_35 AC 583 ms
113,608 KB
testcase_36 AC 606 ms
134,764 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