結果

問題 No.1300 Sum of Inversions
ユーザー AEnAEn
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
51,712 KB
testcase_01 AC 37 ms
52,096 KB
testcase_02 AC 38 ms
51,840 KB
testcase_03 AC 615 ms
128,640 KB
testcase_04 AC 585 ms
128,340 KB
testcase_05 AC 486 ms
129,408 KB
testcase_06 AC 663 ms
131,840 KB
testcase_07 AC 648 ms
132,352 KB
testcase_08 AC 705 ms
154,964 KB
testcase_09 AC 704 ms
155,076 KB
testcase_10 AC 406 ms
135,680 KB
testcase_11 AC 420 ms
135,904 KB
testcase_12 AC 577 ms
128,000 KB
testcase_13 AC 584 ms
127,232 KB
testcase_14 AC 762 ms
184,668 KB
testcase_15 AC 704 ms
154,852 KB
testcase_16 AC 611 ms
128,896 KB
testcase_17 AC 409 ms
129,920 KB
testcase_18 AC 460 ms
137,344 KB
testcase_19 AC 542 ms
124,672 KB
testcase_20 AC 541 ms
125,428 KB
testcase_21 AC 550 ms
125,292 KB
testcase_22 AC 500 ms
129,280 KB
testcase_23 AC 681 ms
132,096 KB
testcase_24 AC 501 ms
126,632 KB
testcase_25 AC 449 ms
137,016 KB
testcase_26 AC 435 ms
136,320 KB
testcase_27 AC 483 ms
132,716 KB
testcase_28 AC 725 ms
161,928 KB
testcase_29 AC 536 ms
125,312 KB
testcase_30 AC 711 ms
155,008 KB
testcase_31 AC 496 ms
129,056 KB
testcase_32 AC 523 ms
126,720 KB
testcase_33 AC 276 ms
109,440 KB
testcase_34 AC 293 ms
106,268 KB
testcase_35 AC 437 ms
142,848 KB
testcase_36 AC 483 ms
183,644 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