結果

問題 No.1300 Sum of Inversions
ユーザー brthyyjpbrthyyjp
提出日時 2020-11-27 22:06:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 523 ms / 2,000 ms
コード長 2,298 bytes
コンパイル時間 301 ms
コンパイル使用メモリ 82,196 KB
実行使用メモリ 172,416 KB
最終ジャッジ日時 2024-07-26 12:55:55
合計ジャッジ時間 15,194 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0