結果

問題 No.1300 Sum of Inversions
コンテスト
ユーザー sasa8uyauya
提出日時 2024-09-19 20:27:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 676 ms / 2,000 ms
コード長 925 bytes
コンパイル時間 149 ms
コンパイル使用メモリ 82,956 KB
実行使用メモリ 178,268 KB
最終ジャッジ日時 2024-09-19 20:28:08
合計ジャッジ時間 17,711 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

class FenwickTree:
  def __init__(self,n):
    self.n=n
    self.st=[0]*n
  
  def add(self,p,x):
    p+=1
    while p<=self.n:
      self.st[p-1]+=x
      p+=p&(-p)
  
  def sum(self,l,r):
    return self._sum(r)-self._sum(l)
  
  def _sum(self,p):
    a=0
    while p>0:
      a+=self.st[p-1]
      p-=p&(-p)
    return a


n=int(input())
a=list(map(int,input().split()))
z=sorted(set(a+[-1,10**10]))
d={v:i for i,v in enumerate(z)}
M=998244353

lc=[0]*n
ls=[0]*n
stc=FenwickTree(len(z))
sts=FenwickTree(len(z))
for i in range(n):
  v=a[i]
  l=d[v]+1
  r=len(z)-1
  lc[i]=stc.sum(l,r+1)
  ls[i]=sts.sum(l,r+1)
  stc.add(d[v],1)
  sts.add(d[v],v)

rc=[0]*n
rs=[0]*n
stc=FenwickTree(len(z))
sts=FenwickTree(len(z))
for i in reversed(range(n)):
  v=a[i]
  l=0
  r=d[v]-1
  rc[i]=stc.sum(l,r+1)
  rs[i]=sts.sum(l,r+1)
  stc.add(d[v],1)
  sts.add(d[v],v)

print(sum(ls[i]*rc[i]+lc[i]*a[i]*rc[i]+lc[i]*rs[i] for i in range(n))%M)
0