結果
問題 | No.2665 Minimize Inversions of Deque |
ユーザー | miya145592 |
提出日時 | 2024-03-08 22:57:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 355 ms / 2,000 ms |
コード長 | 1,988 bytes |
コンパイル時間 | 177 ms |
コンパイル使用メモリ | 82,816 KB |
実行使用メモリ | 109,528 KB |
最終ジャッジ日時 | 2024-09-29 20:28:00 |
合計ジャッジ時間 | 11,312 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
class SegTree:def __init__(self, op, e, n, v=None):self._n = nself._op = opself._e = eself._log = (n - 1).bit_length()self._size = 1 << self._logself._d = [self._e()] * (self._size << 1)if v is not None:for i in range(self._n):self._d[self._size + i] = v[i]for i in range(self._size - 1, 0, -1):self._d[i] = self._op(self._d[i << 1], self._d[i << 1 | 1])def set(self, p, x):p += self._sizeself._d[p] = xwhile p:l, r = p, p^1if l > r: l, r = r, lself._d[p >> 1] = self._op(self._d[l], self._d[r])p >>= 1def get(self, p):return self._d[p + self._size]#[l, r)の区間で求めるdef prod(self, l, r):sml, smr = self._e(), self._e()l += self._sizer += self._sizewhile l < r:if l & 1:sml = self._op(sml, self._d[l])l += 1if r & 1:r -= 1smr = self._op(self._d[r], smr)l >>= 1r >>= 1return self._op(sml, smr)def all_prod(self):return self._d[1]def op(x, y):return x+ydef e():return 0from collections import dequeimport sysinput = sys.stdin.readlineT = int(input())for _ in range(T):N = int(input())P = list(map(int, input().split()))deq = deque()ST = SegTree(op, e, N)x = 0for i, p in enumerate(P):cnt = ST.prod(0, p)small = cntlarge = i-cntif small<large:deq.appendleft(p)x+=smallelif small>large:deq.append(p)x+=largeelse:if len(deq)>0 and deq[0]>p:deq.appendleft(p)else:deq.append(p)x+=smallST.set(p-1, 1)print(x)print(*deq)