結果

問題 No.1300 Sum of Inversions
ユーザー AEn
提出日時 2022-12-24 02:53:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 762 ms / 2,000 ms
コード長 1,430 bytes
コンパイル時間 438 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 184,668 KB
最終ジャッジ日時 2024-11-18 05:06:14
合計ジャッジ時間 21,738 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Binary_Indexed_Tree:
    def __init__(self, n) -> None:
        self._n = n
        self.data = [0] * (n+1)
        self.depth = n.bit_length()

    def add(self, p, x) -> None:
        """任意の要素ai←ai+xを行う O(logn)"""
        assert 0 <= p < self._n
        p += 1
        while p <= self._n:
            self.data[p-1] += x
            p += p & (-p)
    
    def sum(self, l, r) -> int:
        """区間[l,r)で計算"""
        assert 0 <= l <= r <= self._n
        return self._sum(r) - self._sum(l)
    
    def _sum(self, d) -> int:
        sm = 0
        while d > 0:
            sm += self.data[d-1]
            d -= d & (-d)
        return sm

N = int(input())
A = list(map(int,input().split()))
z = {num:i for i, num in enumerate(list(sorted(set(A))))}
n1 = [0]*N
n2 = [0]*N
sm1 = [0]*N
sm2 = [0]*N
BIT1 = Binary_Indexed_Tree(len(z)+5)
BIT1_s = Binary_Indexed_Tree(len(z)+5)
BIT2 = Binary_Indexed_Tree(len(z)+5)
BIT2_s = Binary_Indexed_Tree(len(z)+5)
for i in range(N):
    id1 = z[A[i]]
    id2 = z[A[-1-i]]
    n1[i] = BIT1.sum(id1+1,len(z))
    n2[-1-i] = BIT2._sum(id2)
    sm1[i] = BIT1_s.sum(id1+1,len(z))
    sm2[-1-i] = BIT2_s._sum(id2)
    BIT1.add(id1,1)
    BIT2.add(id2,1)
    BIT1_s.add(id1,A[i])
    BIT2_s.add(id2,A[-1-i])
res = 0
mod = 998244353
for i in range(N):
    if n1[i]>0 and n2[i]>0:
        res += A[i]*n1[i]*n2[i]+sm1[i]*n2[i]+sm2[i]*n1[i]
        res %= mod
print(res)
0