結果

問題 No.1300 Sum of Inversions
ユーザー AEnAEn
提出日時 2022-12-24 02:53:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 790 ms / 2,000 ms
コード長 1,430 bytes
コンパイル時間 1,228 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 184,412 KB
最終ジャッジ日時 2024-04-29 04:47:14
合計ジャッジ時間 22,521 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
52,224 KB
testcase_01 AC 42 ms
52,224 KB
testcase_02 AC 45 ms
52,480 KB
testcase_03 AC 626 ms
128,256 KB
testcase_04 AC 591 ms
128,256 KB
testcase_05 AC 531 ms
128,896 KB
testcase_06 AC 682 ms
148,512 KB
testcase_07 AC 674 ms
132,096 KB
testcase_08 AC 740 ms
155,120 KB
testcase_09 AC 720 ms
154,912 KB
testcase_10 AC 434 ms
135,424 KB
testcase_11 AC 451 ms
135,936 KB
testcase_12 AC 605 ms
127,872 KB
testcase_13 AC 605 ms
127,232 KB
testcase_14 AC 790 ms
184,412 KB
testcase_15 AC 737 ms
154,768 KB
testcase_16 AC 682 ms
128,896 KB
testcase_17 AC 423 ms
130,048 KB
testcase_18 AC 468 ms
137,472 KB
testcase_19 AC 538 ms
124,928 KB
testcase_20 AC 558 ms
125,312 KB
testcase_21 AC 555 ms
125,568 KB
testcase_22 AC 504 ms
129,280 KB
testcase_23 AC 691 ms
131,840 KB
testcase_24 AC 518 ms
126,720 KB
testcase_25 AC 457 ms
137,088 KB
testcase_26 AC 456 ms
136,448 KB
testcase_27 AC 489 ms
134,144 KB
testcase_28 AC 761 ms
161,740 KB
testcase_29 AC 550 ms
125,952 KB
testcase_30 AC 728 ms
155,012 KB
testcase_31 AC 531 ms
129,024 KB
testcase_32 AC 546 ms
126,848 KB
testcase_33 AC 286 ms
109,440 KB
testcase_34 AC 297 ms
106,272 KB
testcase_35 AC 445 ms
142,720 KB
testcase_36 AC 503 ms
183,520 KB
権限があれば一括ダウンロードができます

ソースコード

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