結果
問題 | No.1300 Sum of Inversions |
ユーザー |
![]() |
提出日時 | 2021-10-16 11:22:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 711 ms / 2,000 ms |
コード長 | 1,356 bytes |
コンパイル時間 | 685 ms |
コンパイル使用メモリ | 82,112 KB |
実行使用メモリ | 188,148 KB |
最終ジャッジ日時 | 2024-09-17 19:21:23 |
合計ジャッジ時間 | 21,682 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
N = int(input())A = list(map(int,input().split()))mod = 998244353class Bit1:def __init__(self, n):self.size = nself.tree = [0] * (n + 1)def sum(self, i):s = 0while i > 0:s += self.tree[i]s %= modi -= i & -ireturn sdef add(self, i, x):while i <= self.size:self.tree[i] += xself.tree[i] %= modi += i & -iclass Bit2:def __init__(self, n):self.size = nself.tree = [0] * (n + 1)def sum(self, i):s = 0while i > 0:s += self.tree[i]i -= i & -ireturn sdef add(self, i, x):while i <= self.size:self.tree[i] += xi += i & -iB = list(set(A))B.sort()M = len(B)D = dict(zip(B,range(M)))bit11 = Bit1(M)bit21 = Bit1(M)bit12 = Bit2(M)bit22 = Bit2(M)ans = 0for i in range(N):tmp = bit21.sum(M) - bit21.sum(D[A[i]]+1)cnt = bit22.sum(M) - bit22.sum(D[A[i]]+1)if cnt > 0:ans = (ans + A[i] * cnt + tmp) % modtmp = bit11.sum(M) - bit11.sum(D[A[i]]+1)cnt = bit12.sum(M) - bit12.sum(D[A[i]]+1)if cnt > 0:bit21.add(D[A[i]]+1,tmp + A[i] * cnt)bit22.add(D[A[i]]+1,cnt)bit11.add(D[A[i]]+1,A[i])bit12.add(D[A[i]]+1,1)print(ans)