結果
問題 | No.1300 Sum of Inversions |
ユーザー | brthyyjp |
提出日時 | 2020-11-27 22:06:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 699 ms / 2,000 ms |
コード長 | 2,298 bytes |
コンパイル時間 | 1,059 ms |
コンパイル使用メモリ | 86,924 KB |
実行使用メモリ | 153,160 KB |
最終ジャッジ日時 | 2023-10-01 06:05:09 |
合計ジャッジ時間 | 20,237 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
71,388 KB |
testcase_01 | AC | 74 ms
71,244 KB |
testcase_02 | AC | 76 ms
71,204 KB |
testcase_03 | AC | 553 ms
133,332 KB |
testcase_04 | AC | 533 ms
136,288 KB |
testcase_05 | AC | 449 ms
135,344 KB |
testcase_06 | AC | 595 ms
132,232 KB |
testcase_07 | AC | 561 ms
132,520 KB |
testcase_08 | AC | 637 ms
134,368 KB |
testcase_09 | AC | 623 ms
134,132 KB |
testcase_10 | AC | 381 ms
132,112 KB |
testcase_11 | AC | 386 ms
132,376 KB |
testcase_12 | AC | 530 ms
135,192 KB |
testcase_13 | AC | 540 ms
137,200 KB |
testcase_14 | AC | 699 ms
141,068 KB |
testcase_15 | AC | 654 ms
134,252 KB |
testcase_16 | AC | 560 ms
131,840 KB |
testcase_17 | AC | 368 ms
126,788 KB |
testcase_18 | AC | 414 ms
133,272 KB |
testcase_19 | AC | 473 ms
136,920 KB |
testcase_20 | AC | 489 ms
137,564 KB |
testcase_21 | AC | 488 ms
137,580 KB |
testcase_22 | AC | 451 ms
135,124 KB |
testcase_23 | AC | 611 ms
131,888 KB |
testcase_24 | AC | 453 ms
135,072 KB |
testcase_25 | AC | 405 ms
133,060 KB |
testcase_26 | AC | 408 ms
132,840 KB |
testcase_27 | AC | 439 ms
139,948 KB |
testcase_28 | AC | 653 ms
140,484 KB |
testcase_29 | AC | 486 ms
137,160 KB |
testcase_30 | AC | 626 ms
134,428 KB |
testcase_31 | AC | 448 ms
135,044 KB |
testcase_32 | AC | 468 ms
135,084 KB |
testcase_33 | AC | 297 ms
109,328 KB |
testcase_34 | AC | 296 ms
111,072 KB |
testcase_35 | AC | 440 ms
153,160 KB |
testcase_36 | AC | 461 ms
139,888 KB |
ソースコード
import sys import io, os input = sys.stdin.buffer.readline def main(): n = int(input()) A = list(map(int, input().split())) B = set(A) B = list(B) B.sort() d = {} for i, b in enumerate(B): d[b] = i A = [d[a] for a in A] mod = 998244353 class BIT: def __init__(self, n): self.n = n self.bit = [0]*(self.n+1) # 1-indexed def init(self, init_val): for i, v in enumerate(init_val): self.add(i, v) def add(self, i, x): # i: 0-indexed i += 1 # to 1-indexed while i <= self.n: self.bit[i] += x i += (i & -i) def sum(self, i, j): # return sum of [i, j) # i, j: 0-indexed return self._sum(j) - self._sum(i) def _sum(self, i): # return sum of [0, i) # i: 0-indexed res = 0 while i > 0: res += self.bit[i] i -= i & (-i) return res def lower_bound(self, x): s = 0 pos = 0 depth = self.n.bit_length() v = 1 << depth for i in range(depth, -1, -1): k = pos + v if k <= self.n and s + self.bit[k] < x: s += self.bit[k] pos += v v >>= 1 return pos LC = [0]*n LS = [0]*n bit = BIT(len(B)+1) bitsum = BIT(len(B)+1) for i, a in enumerate(A): c = bit.sum(a+1, bit.n) s = bitsum.sum(a+1, bit.n) LC[i] = c LS[i] = s%mod bit.add(a, 1) bitsum.add(a, B[a]%mod) RC = [0]*n RS = [0]*n bit = BIT(len(B)+1) bitsum = BIT(len(B)+1) for i in reversed(range(n)): a = A[i] c = bit.sum(0, a) s = bitsum.sum(0, a) RC[i] = c RS[i] = s%mod bit.add(a, 1) bitsum.add(a, B[a]%mod) #print(LC) #print(LS) #print(RC) #print(RS) ans = 0 for i, a in enumerate(A): if LC[i] == 0 or RC[i] == 0: continue ans += LS[i]*RC[i]+B[a]*LC[i]*RC[i]+LC[i]*RS[i] ans %= mod print(ans) if __name__ == '__main__': main()