結果
問題 | No.1300 Sum of Inversions |
ユーザー | ayaoni |
提出日時 | 2020-11-27 22:37:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,108 ms / 2,000 ms |
コード長 | 2,494 bytes |
コンパイル時間 | 197 ms |
コンパイル使用メモリ | 82,152 KB |
実行使用メモリ | 188,840 KB |
最終ジャッジ日時 | 2024-07-26 18:58:12 |
合計ジャッジ時間 | 27,861 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
import syssys.setrecursionlimit(10**7)def I(): return int(sys.stdin.readline().rstrip())def MI(): return map(int,sys.stdin.readline().rstrip().split())def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))def LI2(): return list(map(int,sys.stdin.readline().rstrip()))def S(): return sys.stdin.readline().rstrip()def LS(): return list(sys.stdin.readline().rstrip().split())def LS2(): return list(sys.stdin.readline().rstrip())class SegTree: # モノイドに対して適用可能、Nが2冪でなくても良いdef __init__(self,N,seg_func,unit):self.N = 1 << (N-1).bit_length()self.func = seg_funcself.unit = unitself.tree = [self.unit]*(2*self.N)def build(self,init_value): # 初期値を[N,2N)に格納for i in range(len(init_value)):self.tree[i+self.N] = init_value[i]for i in range(self.N-1,0,-1):self.tree[i] = self.func(self.tree[i << 1],self.tree[i << 1 | 1])def set_val(self,i,x): # i番目(0-index)の値をxに変更i += self.Nself.tree[i] = xi >>= 1while i:self.tree[i] = self.func(self.tree[i << 1],self.tree[i << 1 | 1])i >>= 1def fold(self,L,R): # [L,R)の区間取得L += self.NR += self.NvL = self.unitvR = self.unitwhile L < R:if L & 1:vL = self.func(vL,self.tree[L])L += 1if R & 1:R -= 1vR = self.func(self.tree[R],vR)L >>= 1R >>= 1return self.func(vL,vR)def seg_func(x,y):x0,x1 = xy0,y1 = yreturn ((x0+y0) % mod,(x1+y1) % mod)N = I()A = LI()mod = 998244353AA = sorted(list(set(A)))d = {}M = len(AA)for i in range(M):d[AA[i]] = iST_left = SegTree(N,seg_func,(0,0))X_left = []for i in range(N):a = d[A[i]]ST_left.set_val(a,seg_func((A[i],1),ST_left.tree[a+ST_left.N]))if 1 <= i <= N-2:X_left.append(ST_left.fold(a+1,N))ST_right = SegTree(N,seg_func,(0,0))X_right = []for i in range(N-1,-1,-1):a = d[A[i]]ST_right.set_val(a,seg_func((A[i],1),ST_right.tree[a+ST_right.N]))if 1 <= i <= N-2:X_right.append(ST_right.fold(0,a))X_right.reverse()ans = 0for i in range(1,N-1):a = A[i]x,y = X_left[i-1]z,w = X_right[i-1]if y > 0 and w > 0:ans += a*(y*w)+w*x+y*zans %= modprint(ans)