結果
問題 | No.1300 Sum of Inversions |
ユーザー |
![]() |
提出日時 | 2020-11-27 21:46:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 767 ms / 2,000 ms |
コード長 | 1,240 bytes |
コンパイル時間 | 1,115 ms |
コンパイル使用メモリ | 82,092 KB |
実行使用メモリ | 129,736 KB |
最終ジャッジ日時 | 2024-07-26 12:10:57 |
合計ジャッジ時間 | 18,828 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
class BIT(): def __init__(self, init): if type(init) == int: self.n = init + 1 self.X = [0] * self.n else: self.n = len(init) + 1 self.X = [0] + init for i in range(1, self.n): if i + (i & -i) < self.n: self.X[i + (i & -i)] += self.X[i] def add(self, i, x=1): i += 1 while i < self.n: self.X[i] += x i += i & (-i) def getsum(self, i): ret = 0 while i != 0: ret += self.X[i] i -= i&(-i) return ret def getrange(self, l, r): return self.getsum(r) - self.getsum(l) def calc(L, r = 0): bit = BIT(N) X = [0] * N for aa in L: a, i = aa >> 18, aa & m X[i] = bit.getrange(i, N) if r == 0 else bit.getsum(i) bit.add(i, (a << 18) + 1) return X m = (1 << 18) - 1 N = int(input()) A = [int(a) for a in input().split()] AA = sorted([(int(a) << 18) + i for i, a in enumerate(A)]) X = calc(AA) Y = calc(AA[::-1], 1) ans = 0 for a, x, y in zip(A, X, Y): a1, c1 = x >> 18, x & m a2, c2 = y >> 18, y & m ans += a1 * c2 + a2 * c1 + a * c1 * c2 print(ans % 998244353)