結果
問題 | No.1300 Sum of Inversions |
ユーザー |
![]() |
提出日時 | 2020-11-27 21:58:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,025 ms / 2,000 ms |
コード長 | 1,158 bytes |
コンパイル時間 | 350 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 112,384 KB |
最終ジャッジ日時 | 2024-07-26 12:35:14 |
合計ジャッジ時間 | 25,171 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
import sysinput = sys.stdin.readlineN = int(input())a = list(map(int, input().split()))mod = 998244353class FenwickTree:def __init__(self, n):self.n = nself.data = [0] * (n + 2)def sum(self, l, r):s = 0while l > 0:s -= self.data[l]l -= l & -lwhile r > 0:s += self.data[r]r -= r & -rreturn sdef add(self, i, x):i += 1while i <= self.n:self.data[i] += xi += i & -idef lowerbound(self, s):x = 0y = 0for i in range(self.n.bit_length(), -1, -1):k = x + (1 << i)if k <= self.n and (y + self.data[k] < s):y += self.data[k]x += 1 << ireturn x + 1fwk = FenwickTree(N)fwk2 = FenwickTree(N)sa = [(a[i], i) for i in range(N)]sa.sort(reverse = True)table = [0] * Ntable2 = [0] * Nfor x, i in sa:table[i] = fwk.sum(0, i) % modtable2[i] = fwk2.sum(0, i)fwk.add(i, x)fwk2.add(i, 1)#print(table, table2)fwk = FenwickTree(N)fwk2 = FenwickTree(N)res = 0for x, i in sa:res += fwk.sum(0, i) + fwk2.sum(0, i) * xres %= modfwk.add(i, table[i] + table2[i] * x)fwk2.add(i, table2[i])print(res)