結果
問題 | No.1300 Sum of Inversions |
ユーザー |
![]() |
提出日時 | 2020-11-27 22:12:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 708 ms / 2,000 ms |
コード長 | 1,063 bytes |
コンパイル時間 | 232 ms |
コンパイル使用メモリ | 82,252 KB |
実行使用メモリ | 173,784 KB |
最終ジャッジ日時 | 2024-07-26 13:07:05 |
合計ジャッジ時間 | 17,554 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
def coordinate_compression(arr):return {v: k for k, v in enumerate(sorted(set(arr)))}n = int(input())bit = [0] * (n + 4)def add(a, i):while i <= n:bit[i] += ai += i & -idef query(i):res = 0while i > 0:res += bit[i]i -= i & -ireturn resa = list(map(int, input().split()))c = coordinate_compression(a)p = [0] * nd = [1] * nfor i in range(n):x = a[i]p[i] += query(n - c[x])if d[i]:d[i] = 0add(x, n-c[x]+1)bit = [0] * (n + 4)q = [0] * nd = [1] * nfor i in range(n - 1, -1, -1):x = a[i]q[i] += query(c[x]+1)if d[i]:d[i] = 0add(x, c[x] + 2)ans = 0bit = [0] * (n + 4)pp = [0] * nd = [1] * nfor i in range(n):x = a[i]pp[i] += query(n - c[x])add(1, n - c[x]+1)bit = [0] * (n + 4)qq = [0] * nd = [1] * nfor i in range(n - 1, -1, -1):x = a[i]qq[i] += query(c[x]+1)add(1, c[x] + 2)for i in range(n):ans += p[i] * qq[i] + q[i] * pp[i] + a[i] * pp[i] * qq[i]print(ans % 998244353)