結果
問題 | No.1300 Sum of Inversions |
ユーザー | shobonvip |
提出日時 | 2022-07-29 21:07:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 963 ms / 2,000 ms |
コード長 | 913 bytes |
コンパイル時間 | 327 ms |
コンパイル使用メモリ | 87,004 KB |
実行使用メモリ | 178,972 KB |
最終ジャッジ日時 | 2023-09-26 18:15:50 |
合計ジャッジ時間 | 27,714 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
71,000 KB |
testcase_01 | AC | 72 ms
71,236 KB |
testcase_02 | AC | 73 ms
71,244 KB |
testcase_03 | AC | 802 ms
137,676 KB |
testcase_04 | AC | 754 ms
124,888 KB |
testcase_05 | AC | 647 ms
116,212 KB |
testcase_06 | AC | 867 ms
163,848 KB |
testcase_07 | AC | 830 ms
144,056 KB |
testcase_08 | AC | 904 ms
169,088 KB |
testcase_09 | AC | 899 ms
168,776 KB |
testcase_10 | AC | 545 ms
113,028 KB |
testcase_11 | AC | 554 ms
113,084 KB |
testcase_12 | AC | 772 ms
136,540 KB |
testcase_13 | AC | 754 ms
125,260 KB |
testcase_14 | AC | 963 ms
178,972 KB |
testcase_15 | AC | 906 ms
168,704 KB |
testcase_16 | AC | 789 ms
138,160 KB |
testcase_17 | AC | 516 ms
109,344 KB |
testcase_18 | AC | 595 ms
113,004 KB |
testcase_19 | AC | 676 ms
120,260 KB |
testcase_20 | AC | 704 ms
120,092 KB |
testcase_21 | AC | 725 ms
120,080 KB |
testcase_22 | AC | 750 ms
116,168 KB |
testcase_23 | AC | 853 ms
163,832 KB |
testcase_24 | AC | 664 ms
115,992 KB |
testcase_25 | AC | 578 ms
113,492 KB |
testcase_26 | AC | 579 ms
113,144 KB |
testcase_27 | AC | 631 ms
116,032 KB |
testcase_28 | AC | 935 ms
177,288 KB |
testcase_29 | AC | 690 ms
120,344 KB |
testcase_30 | AC | 905 ms
169,036 KB |
testcase_31 | AC | 653 ms
116,172 KB |
testcase_32 | AC | 669 ms
116,028 KB |
testcase_33 | AC | 516 ms
110,692 KB |
testcase_34 | AC | 529 ms
109,912 KB |
testcase_35 | AC | 581 ms
139,508 KB |
testcase_36 | AC | 603 ms
178,068 KB |
ソースコード
mod = 998244353 class BIT: def query(self, m): res = 0 while m > 0: res = (res + self.bit[m]) % mod m -= m&(-m) return res def sum(self, a, b): return (self.query(b)-self.query(a)) % mod def add(self, m, x): m += 1 bitlen = len(self.bit) while m <= bitlen-1: self.bit[m] = (self.bit[m] + x) % mod m += m&(-m) return def __init__(self, a): self.bitlen = a self.bit = [0]*a n = int(input()) a = list(map(int,input().split())) def compress(arr): *XS, = set(arr) XS.sort() return {cmp_e: cmp_i for cmp_i, cmp_e in enumerate(XS)} a_c = compress(a) bitv = BIT(n+1) bit1 = BIT(n+1) bitw = BIT(n+1) bit2 = BIT(n+1) ans = 0 for i in range(n): targ = a_c[a[i]] ans = (ans+bit2.sum(targ+1,n)+a[i]*bitw.sum(targ+1,n))%mod bit2.add(targ,(bit1.sum(targ+1,n)+a[i]*bitv.sum(targ+1,n))%mod) bitw.add(targ,bitv.sum(targ+1,n)) bit1.add(targ,a[i]) bitv.add(targ,1) print(ans)