結果
問題 | No.2665 Minimize Inversions of Deque |
ユーザー | minimum |
提出日時 | 2024-03-08 21:40:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 374 ms / 2,000 ms |
コード長 | 1,356 bytes |
コンパイル時間 | 1,084 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 108,160 KB |
最終ジャッジ日時 | 2024-09-29 19:11:09 |
合計ジャッジ時間 | 11,958 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
from collections import dequeclass FenwickTree:def __init__(self, N):self.N = Nself.d = [0] * Ndef add(self, p, x):assert 0 <= p < self.Np += 1while p <= self.N:self.d[p - 1] += xp += p & (-p)def sum0(self, r):s = 0while r > 0:s += self.d[r - 1]r -= r & (-r)return sdef get_sum(self, l, r):assert 0 <= l <= r <= self.Nreturn self.sum0(r) - self.sum0(l)def solve():N = int(input())P = list(map(lambda x: x - 1, map(int, input().split())))fw = FenwickTree(N)dq = deque()ans = 0for i in range(N):l = fw.get_sum(0, P[i])r = fw.get_sum(P[i], N)fw.add(P[i], 1)if l < r:dq.appendleft(P[i] + 1)ans += lelif l > r:dq.append(P[i] + 1)ans += relse:if i == 0:dq.append(P[i] + 1)continuetop = dq.popleft()dq.appendleft(top)if P[i] < top:dq.appendleft(P[i] + 1)ans += lelse:dq.append(P[i] + 1)ans += rprint(ans)print(*dq)T = int(input())for _ in range(T):solve()