結果
問題 | No.1300 Sum of Inversions |
ユーザー |
![]() |
提出日時 | 2020-11-27 23:04:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 728 ms / 2,000 ms |
コード長 | 934 bytes |
コンパイル時間 | 631 ms |
コンパイル使用メモリ | 82,576 KB |
実行使用メモリ | 181,432 KB |
最終ジャッジ日時 | 2024-07-26 19:26:45 |
合計ジャッジ時間 | 19,090 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
mod = 998244353 def BIT_query(BIT,idx): res_sum = 0 while idx > 0: res_sum += BIT[idx] idx -= idx&(-idx) return res_sum % mod def BIT_update(BIT,idx,x): while idx <= N: BIT[idx] += x BIT[idx] %= mod idx += idx&(-idx) return def compress(li): *XS, = set(li) XS.sort() return {e: i for i, e in enumerate(XS)} N = int(input()) A = list(map(int,input().split()))[::-1] cA = compress(A) ans = 0 BIT1 = [0]*(N+1) BIT2 = [0]*(N+1) BIT3 = [0]*(N+1) BIT4 = [0]*(N+1) for i in range(N): c = cA[A[i]]+1 if c > 1: ans += BIT_query(BIT4,c-1) ans += BIT_query(BIT3,c-1)*A[i] ans %= mod BIT_update(BIT1,c,1) BIT_update(BIT2,c,A[i]) num = 0 SUM = 0 if c > 1: num = BIT_query(BIT1,c-1) SUM = BIT_query(BIT2,c-1) BIT_update(BIT3,c,num) BIT_update(BIT4,c,A[i]*num) BIT_update(BIT4,c,SUM) print(ans)