結果

問題 No.1300 Sum of Inversions
ユーザー zkouzkou
提出日時 2020-11-27 21:53:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 917 ms / 2,000 ms
コード長 1,904 bytes
コンパイル時間 333 ms
コンパイル使用メモリ 86,700 KB
実行使用メモリ 177,956 KB
最終ジャッジ日時 2023-10-01 05:29:44
合計ジャッジ時間 25,105 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 76 ms
71,168 KB
testcase_01 AC 76 ms
71,172 KB
testcase_02 AC 75 ms
71,108 KB
testcase_03 AC 732 ms
149,944 KB
testcase_04 AC 716 ms
149,408 KB
testcase_05 AC 601 ms
122,616 KB
testcase_06 AC 806 ms
160,476 KB
testcase_07 AC 787 ms
157,708 KB
testcase_08 AC 852 ms
167,360 KB
testcase_09 AC 852 ms
166,640 KB
testcase_10 AC 507 ms
113,540 KB
testcase_11 AC 495 ms
113,392 KB
testcase_12 AC 709 ms
149,588 KB
testcase_13 AC 700 ms
148,668 KB
testcase_14 AC 917 ms
177,956 KB
testcase_15 AC 839 ms
166,716 KB
testcase_16 AC 749 ms
150,476 KB
testcase_17 AC 501 ms
109,228 KB
testcase_18 AC 557 ms
117,384 KB
testcase_19 AC 651 ms
140,940 KB
testcase_20 AC 657 ms
141,256 KB
testcase_21 AC 651 ms
141,332 KB
testcase_22 AC 599 ms
123,180 KB
testcase_23 AC 809 ms
161,000 KB
testcase_24 AC 616 ms
123,672 KB
testcase_25 AC 541 ms
117,820 KB
testcase_26 AC 535 ms
117,096 KB
testcase_27 AC 588 ms
122,700 KB
testcase_28 AC 884 ms
176,380 KB
testcase_29 AC 656 ms
141,248 KB
testcase_30 AC 848 ms
166,684 KB
testcase_31 AC 608 ms
122,516 KB
testcase_32 AC 615 ms
123,504 KB
testcase_33 AC 367 ms
128,340 KB
testcase_34 AC 383 ms
143,528 KB
testcase_35 AC 543 ms
170,780 KB
testcase_36 AC 549 ms
177,748 KB
権限があれば一括ダウンロードができます

ソースコード

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