結果
問題 | No.1300 Sum of Inversions |
ユーザー | shotoyoo |
提出日時 | 2020-11-27 22:40:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 641 ms / 2,000 ms |
コード長 | 2,340 bytes |
コンパイル時間 | 263 ms |
コンパイル使用メモリ | 87,316 KB |
実行使用メモリ | 148,164 KB |
最終ジャッジ日時 | 2023-10-09 20:45:04 |
合計ジャッジ時間 | 18,051 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 78 ms
71,112 KB |
testcase_01 | AC | 76 ms
71,488 KB |
testcase_02 | AC | 76 ms
71,532 KB |
testcase_03 | AC | 505 ms
120,784 KB |
testcase_04 | AC | 489 ms
123,204 KB |
testcase_05 | AC | 413 ms
117,804 KB |
testcase_06 | AC | 561 ms
134,408 KB |
testcase_07 | AC | 551 ms
134,680 KB |
testcase_08 | AC | 600 ms
137,092 KB |
testcase_09 | AC | 592 ms
137,016 KB |
testcase_10 | AC | 359 ms
112,500 KB |
testcase_11 | AC | 365 ms
112,300 KB |
testcase_12 | AC | 490 ms
122,640 KB |
testcase_13 | AC | 481 ms
122,480 KB |
testcase_14 | AC | 641 ms
145,572 KB |
testcase_15 | AC | 582 ms
138,224 KB |
testcase_16 | AC | 507 ms
128,380 KB |
testcase_17 | AC | 339 ms
108,936 KB |
testcase_18 | AC | 372 ms
113,688 KB |
testcase_19 | AC | 429 ms
120,604 KB |
testcase_20 | AC | 440 ms
120,816 KB |
testcase_21 | AC | 434 ms
120,896 KB |
testcase_22 | AC | 397 ms
117,868 KB |
testcase_23 | AC | 555 ms
136,472 KB |
testcase_24 | AC | 406 ms
117,812 KB |
testcase_25 | AC | 366 ms
113,044 KB |
testcase_26 | AC | 360 ms
112,764 KB |
testcase_27 | AC | 399 ms
117,828 KB |
testcase_28 | AC | 606 ms
143,560 KB |
testcase_29 | AC | 443 ms
120,748 KB |
testcase_30 | AC | 592 ms
137,248 KB |
testcase_31 | AC | 405 ms
117,804 KB |
testcase_32 | AC | 415 ms
118,296 KB |
testcase_33 | AC | 295 ms
115,640 KB |
testcase_34 | AC | 312 ms
131,964 KB |
testcase_35 | AC | 473 ms
141,800 KB |
testcase_36 | AC | 509 ms
148,164 KB |
ソースコード
import sys input = lambda : sys.stdin.readline().rstrip() sys.setrecursionlimit(max(1000, 10**9)) write = lambda x: sys.stdout.write(x+"\n") class BIT: ### BIT binary def __init__(self, n, values=None): self.bit = [0]*(n+1) self.n = n if values is not None: for i,v in enumerate(values): self.add(i,v) #a1 ~ aiまでの和 O(logn) def query(self,i): res = 0 while i > 0: res += self.bit[i] i -= i&(-i) return res #ai += x(logN) def add(self,i,x): i += 1 if i==0: raise RuntimeError while i <= len(self.bit)-1: self.bit[i] += x i += i&(-i) def check(self): l = [] prv = 0 for i in range(1,self.n+1): val = self.query(i) l.append(val-prv) prv = val print(" ".join(map(str, l))) def index(self, v): """a0,...,aiの和がv以上になる最小のindexを求める 存在しないとき配列サイズを返す """ if v <= 0: return 0 x = 0 r = 1 while r < n: r = r << 1; ll = r while ll>0: if x+ll<n and self.bit[x+ll]<v: v -= self.bit[x+ll] x += ll ll = ll>>1 return x from bisect import bisect_left def press(l): # xs[inds[i]]==l[i]となる xs = sorted(set(l)) inds = [None] * len(l) for i,item in enumerate(l): inds[i] = bisect_left(xs, item) return xs, inds M = 998244353 n = int(input()) a = list(map(int, input().split())) xs, inds = press(a) m = len(xs) bit = BIT(m) v0 = [] for i,v in enumerate(inds): v0.append(i - bit.query(v+1)) bit.add(v, 1) bit = BIT(m) v1 = [] for i,v in enumerate(inds[::-1]): v1.append(bit.query(v)) bit.add(v, 1) v1 = v1[::-1] bit = BIT(m) c1 = [] for i in range(n-1,-1,-1): v = inds[i] c1.append(bit.query(v)) bit.add(v, v1[i]) c1 = c1[::-1] bit = BIT(m) c0 = [] tmp = 0 for i in range(n): v = inds[i] c0.append(tmp-bit.query(v+1)) bit.add(v, v0[i]) tmp += v0[i] ans = 0 for i in range(n): ans += a[i]*v0[i]*v1[i] # print(ans) # for i in range(n): ans += a[i]*(c0[i] + c1[i]) ans %= M print(ans)