結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー |
![]() |
提出日時 | 2023-09-05 12:18:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,841 ms / 3,000 ms |
コード長 | 1,591 bytes |
コンパイル時間 | 227 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 218,396 KB |
最終ジャッジ日時 | 2024-06-23 07:57:50 |
合計ジャッジ時間 | 11,773 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 13 |
ソースコード
import sysinput = sys.stdin.readlinefrom copy import *from bisect import *def compress(lst):"""B: lstを座圧したリストD: indexから元の値を取得する辞書"""B = []D = dict()vals = deepcopy(lst)vals = list(set(vals))vals.sort()for i in range(len(lst)):ind = bisect_left(vals, lst[i])B.append(ind)for i in range(len(B)):D[lst[i]] = B[i]return B, D, valsclass Fenwick_Tree:def __init__(self, n):self._n = nself.data = [0] * ndef add(self, p, x):assert 0 <= p < self._np += 1while p <= self._n:self.data[p - 1] += xp += p & -pdef sum(self, l, r):assert 0 <= l <= r <= self._nreturn self._sum(r) - self._sum(l)def _sum(self, r):s = 0while r > 0:s += self.data[r - 1]r -= r & -rreturn sdef get(self, k):k += 1x, r = 0, 1while r < self._n:r <<= 1len = rwhile len:if x + len - 1 < self._n:if self.data[x + len - 1] < k:k -= self.data[x + len - 1]x += lenlen >>= 1return xN = int(input())T = Fenwick_Tree(N + 2)A = [0] * Nfor i in range(N):A[i] = int(input())A, _, _ = compress(A)ans = 0for i in range(N):ans += T.sum(A[i] + 1, N)T.add(A[i], 1)for i in range(N):print(ans)ans += T.sum(A[i] + 1, N) - T.sum(0, A[i])