結果
問題 | No.1300 Sum of Inversions |
ユーザー | tamato |
提出日時 | 2020-11-27 21:52:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 609 ms / 2,000 ms |
コード長 | 2,079 bytes |
コンパイル時間 | 466 ms |
コンパイル使用メモリ | 82,356 KB |
実行使用メモリ | 125,496 KB |
最終ジャッジ日時 | 2024-07-26 12:22:19 |
合計ジャッジ時間 | 17,058 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
mod = 998244353eps = 10**-9def main():import sysinput = sys.stdin.readlineclass Bit:def __init__(self, n):self.size = nself.tree = [0] * (n + 1)def sum(self, i):s = 0while i > 0:s += self.tree[i]i -= i & -ireturn sdef add(self, i, x):while i <= self.size:self.tree[i] += xi += i & -idef lower_bound(self, w):if w <= 0:return 0x = 0k = 1 << (self.size.bit_length() - 1)while k:if x + k <= self.size and self.tree[x + k] < w:w -= self.tree[x + k]x += kk >>= 1return x + 1N = int(input())A = list(map(int, input().split()))A = [(a, i+1) for i, a in enumerate(A)]bit_val = Bit(N)bit_num = Bit(N)A.sort(key=lambda x: x[0], reverse=True)prev = -1L_val = [0] * (N+1)L_num = [0] * (N+1)cnt = 0for a, i in A:if a == prev:cnt += 1else:cnt = 0prev = aL_val[i] = bit_val.sum(i) - a * cntL_num[i] = bit_num.sum(i) - cntbit_val.add(i, a)bit_num.add(i, 1)bit_val = Bit(N)bit_num = Bit(N)A.reverse()prev = -1R_val = [0] * (N + 1)R_num = [0] * (N + 1)cnt = 0S_val = 0S_num = 0for a, i in A:if a == prev:cnt += 1else:cnt = 0prev = aR_val[i] = S_val - bit_val.sum(i) - a * cntR_num[i] = S_num - bit_num.sum(i) - cntbit_val.add(i, a)bit_num.add(i, 1)S_val += aS_num += 1ans = 0for a, i in A:ans = (ans + ((a * L_num[i])%mod * R_num[i])%mod)%modans = (ans + (L_val[i] * R_num[i])%mod)%modans = (ans + (R_val[i] * L_num[i])%mod)%modprint(ans)if __name__ == '__main__':main()