結果

問題 No.1300 Sum of Inversions
ユーザー zkouzkou
提出日時 2020-11-27 21:53:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 910 ms / 2,000 ms
コード長 1,904 bytes
コンパイル時間 262 ms
コンパイル使用メモリ 81,884 KB
実行使用メモリ 172,384 KB
最終ジャッジ日時 2024-07-26 12:24:01
合計ジャッジ時間 23,934 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

class BIT():

    __slots__ = ["func", "e", "n", "data"]

    def __init__(self, length_or_list, func, e):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.n = length_or_list + 1
            self.data = [self.e] * self.n
        else:
            self.n = len(length_or_list) + 1
            self.data = [self.e] + length_or_list
            for i in range(1, self.n):
                if i + (i & -i) < self.n:
                    self.data[i + (i & -i)] = self.func(self.data[i + (i & -i)], self.data[i])        

    def point_append(self, index, delta):
        index += 1
        while index < self.n:
            self.data[index] = self.func(self.data[index], delta)
            index += index & -index
        
    def prefix_folded(self, end):
        res = 0
        while end > 0:
            res = self.func(res, self.data[end])
            end -= end & -end
        return res

from operator import add

MOD = 998244353

N = int(input())
As = list(map(int, input().split()))

a2A = sorted(set(As))
A2a = {A: a for a, A in enumerate(a2A)}

def modadd(a, b):
    return (a + b) % MOD


ansi = []
cnti = []
ansk = []
cntk = []


cnt_bit = BIT(N, add, 0)
A_bit = BIT(N, modadd, 0)
for A in As:
    a = A2a[A]
    ansi.append(A_bit.prefix_folded(N - a))
    cnti.append(cnt_bit.prefix_folded(N - a))
    A_bit.point_append(N - a, A)
    cnt_bit.point_append(N - a, 1)

cnt_bit = BIT(N, add, 0)
A_bit = BIT(N, modadd, 0)
for A in reversed(As):
    a = A2a[A]
    ansk.append(A_bit.prefix_folded(a))
    cntk.append(cnt_bit.prefix_folded(a))
    A_bit.point_append(a, A)
    cnt_bit.point_append(a, 1)

ansk = ansk[::-1]
cntk = cntk[::-1]

# print(ansi, ansk, cnti, cntk)

ans = 0
for ai, ci, ak, ck, A in zip(ansi, cnti, ansk, cntk, As):
    ans += ci * ck * A % MOD
    ans += ci * ak % MOD
    ans += ai * ck % MOD
    ans %= MOD

print(ans)
0