結果
問題 | No.1300 Sum of Inversions |
ユーザー | Kiri8128 |
提出日時 | 2020-11-27 21:46:22 |
言語 | PyPy3 (7.3.13) |
結果 |
AC
|
実行時間 | 698 ms / 2,000 ms |
コード長 | 1,240 bytes |
コンパイル時間 | 1,006 ms |
コンパイル使用メモリ | 86,660 KB |
実行使用メモリ | 141,596 KB |
最終ジャッジ日時 | 2023-10-01 05:16:33 |
合計ジャッジ時間 | 18,089 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 75 ms
71,196 KB |
testcase_01 | AC | 72 ms
71,340 KB |
testcase_02 | AC | 72 ms
71,260 KB |
testcase_03 | AC | 612 ms
114,804 KB |
testcase_04 | AC | 604 ms
114,304 KB |
testcase_05 | AC | 317 ms
100,800 KB |
testcase_06 | AC | 583 ms
120,480 KB |
testcase_07 | AC | 571 ms
118,612 KB |
testcase_08 | AC | 616 ms
130,772 KB |
testcase_09 | AC | 599 ms
130,212 KB |
testcase_10 | AC | 269 ms
97,452 KB |
testcase_11 | AC | 276 ms
97,180 KB |
testcase_12 | AC | 546 ms
114,544 KB |
testcase_13 | AC | 527 ms
114,148 KB |
testcase_14 | AC | 698 ms
135,976 KB |
testcase_15 | AC | 608 ms
122,656 KB |
testcase_16 | AC | 621 ms
116,228 KB |
testcase_17 | AC | 292 ms
95,184 KB |
testcase_18 | AC | 331 ms
98,128 KB |
testcase_19 | AC | 494 ms
107,600 KB |
testcase_20 | AC | 467 ms
108,912 KB |
testcase_21 | AC | 485 ms
107,792 KB |
testcase_22 | AC | 321 ms
100,524 KB |
testcase_23 | AC | 603 ms
120,264 KB |
testcase_24 | AC | 322 ms
100,816 KB |
testcase_25 | AC | 285 ms
97,744 KB |
testcase_26 | AC | 281 ms
97,428 KB |
testcase_27 | AC | 315 ms
100,796 KB |
testcase_28 | AC | 673 ms
131,900 KB |
testcase_29 | AC | 477 ms
107,852 KB |
testcase_30 | AC | 634 ms
129,860 KB |
testcase_31 | AC | 315 ms
100,768 KB |
testcase_32 | AC | 341 ms
101,052 KB |
testcase_33 | AC | 285 ms
110,944 KB |
testcase_34 | AC | 464 ms
110,180 KB |
testcase_35 | AC | 268 ms
113,500 KB |
testcase_36 | AC | 600 ms
141,596 KB |
ソースコード
class BIT(): def __init__(self, init): if type(init) == int: self.n = init + 1 self.X = [0] * self.n else: self.n = len(init) + 1 self.X = [0] + init for i in range(1, self.n): if i + (i & -i) < self.n: self.X[i + (i & -i)] += self.X[i] def add(self, i, x=1): i += 1 while i < self.n: self.X[i] += x i += i & (-i) def getsum(self, i): ret = 0 while i != 0: ret += self.X[i] i -= i&(-i) return ret def getrange(self, l, r): return self.getsum(r) - self.getsum(l) def calc(L, r = 0): bit = BIT(N) X = [0] * N for aa in L: a, i = aa >> 18, aa & m X[i] = bit.getrange(i, N) if r == 0 else bit.getsum(i) bit.add(i, (a << 18) + 1) return X m = (1 << 18) - 1 N = int(input()) A = [int(a) for a in input().split()] AA = sorted([(int(a) << 18) + i for i, a in enumerate(A)]) X = calc(AA) Y = calc(AA[::-1], 1) ans = 0 for a, x, y in zip(A, X, Y): a1, c1 = x >> 18, x & m a2, c2 = y >> 18, y & m ans += a1 * c2 + a2 * c1 + a * c1 * c2 print(ans % 998244353)