結果
問題 | No.1300 Sum of Inversions |
ユーザー |
|
提出日時 | 2023-02-17 20:32:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,974 ms / 2,000 ms |
コード長 | 1,641 bytes |
コンパイル時間 | 197 ms |
コンパイル使用メモリ | 82,236 KB |
実行使用メモリ | 141,824 KB |
最終ジャッジ日時 | 2024-07-19 11:38:40 |
合計ジャッジ時間 | 51,246 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
import sysfrom collections import deque, Counterinput = lambda: sys.stdin.readline().rstrip()ii = lambda: int(input())mi = lambda: map(int, input().split())li = lambda: list(mi())inf = 2 ** 63 - 1mod = 998244353class fenwick_tree():n=1data=[0 for i in range(n)]def __init__(self,N):self.n=Nself.data=[0 for i in range(N)]def add(self,p,x):assert 0<=p<self.n,"0<=p<n,p={0},n={1}".format(p,self.n)p+=1while(p<=self.n):self.data[p-1]+=xp += p&(-p)def sum(self,l,r):assert (0<=l and l<=r and r<=self.n),"0<=l<=r<=n,l={0},r={1},n={2}".format(l,r,self.n)return self.sum0(r)-self.sum0(l)def sum0(self,r):s=0while(r>0):s+=self.data[r-1]r-=r&-rreturn sdef __getitem__(self, p):if isinstance(p, int):return self.sum(p, p + 1)else:return self.sum(p.start, p.stop)def __setitem__(self, p, x):return self.add(p, x - self[p])n = ii()a = li()sa = list(set(a))A = [(sa[i], i) for i in range(len(sa))]A.sort()d = {}sn = len(A)for i in range(sn):d[A[i][0]] = if1 = fenwick_tree(sn)c1 = fenwick_tree(sn)f2 = fenwick_tree(sn)c2 = fenwick_tree(sn)ans = 0for i in range(n):f2[d[a[i]]] += a[i]c2[d[a[i]]] += 1for i in range(n):f2[d[a[i]]] -= a[i]c2[d[a[i]]] -= 1ans += f1[d[a[i]] + 1: sn] * c2[0:d[a[i]]] + f2[0:d[a[i]]] * c1[d[a[i]] + 1: sn] + c1[d[a[i]] + 1: sn] * c2[0:d[a[i]]] * a[i]ans %= modf1[d[a[i]]] += a[i]c1[d[a[i]]] += 1print(ans)