結果

問題 No.1300 Sum of Inversions
ユーザー nehan_der_thalnehan_der_thal
提出日時 2020-11-27 22:25:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 752 ms / 2,000 ms
コード長 949 bytes
コンパイル時間 368 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 177,008 KB
最終ジャッジ日時 2024-07-26 18:42:43
合計ジャッジ時間 19,684 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

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

A = list(map(int, input().split()))
d = dict()
sA = sorted(list(set(A)))
la = len(sA)
for i, x in enumerate(sA):
    d[x]=i+1

bt = Bit(la)
bt2 = Bit(la)
X = [0]*N
for i, a in enumerate(A):
    X[i] = (bt.sum(la)-bt.sum(d[a]), bt2.sum(la)-bt2.sum(d[a]))
    bt.add(d[a], 1)
    bt2.add(d[a], a)
bt = Bit(la)
bt2 = Bit(la)
Y = [0]*N
for i in range(N-1, -1, -1):
    a = A[i]
    Y[i] = (bt.sum(d[a]-1), bt2.sum(d[a]-1))
    bt.add(d[a], 1)
    bt2.add(d[a], a)

MOD =  998244353
R = 0
for i in range(N):
    a, b = X[i]
    c, d = Y[i]
    R = (R + A[i]*a*c + b*c + d*a)%MOD
print(R)
0