結果

問題 No.2665 Minimize Inversions of Deque
ユーザー flygonflygon
提出日時 2024-03-08 21:49:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 385 ms / 2,000 ms
コード長 5,108 bytes
コンパイル時間 498 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 112,276 KB
最終ジャッジ日時 2024-09-29 19:29:48
合計ジャッジ時間 13,448 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
sys.setrecursionlimit(5*10**5)
input = sys.stdin.readline
from collections import defaultdict, deque, Counter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right
from math import gcd
def add(x, y):
return x + y
def e(a):
if a == min:
return 10**18
if a == max:
return -10**18
if a == add:
return 0
class SegTree:
def __init__(self, segf, init_val):
n = len(init_val)
self.segf = segf
self.e = e(segf)
self.seg_len = 1 << n.bit_length()
self.seg = [self.e] * (self.seg_len<<1)
for i in range(n):
self.seg[i + self.seg_len] = init_val[i]
for i in range(self.seg_len)[::-1]:
self.seg[i] = segf(self.seg[i << 1], self.seg[i << 1 | 1])
def point_add(self, pos, x):
pos += self.seg_len
self.seg[pos] += x
while True:
pos >>= 1
if not pos:
break
self.seg[pos] = self.segf(
self.seg[pos << 1], self.seg[pos << 1 | 1])
def point_update(self, pos, x):
pos += self.seg_len
self.seg[pos] = x
while True:
pos >>= 1
if not pos:
break
self.seg[pos] = self.segf(
self.seg[pos << 1], self.seg[pos << 1 | 1])
def get_range(self, l, r):
l += self.seg_len
r += self.seg_len
res = self.e
while l < r:
if l & 1:
res = self.segf(res, self.seg[l])
l += 1
if r & 1:
r -= 1
res = self.segf(res, self.seg[r])
l >>= 1
r >>= 1
return res
# max_right
def j(self, now, i, t):
return self.segf(now, self.seg[i]) >= t
# -1
# [ql,ans)ans
def max_right(self,ql,qr,t):
l = ql + self.seg_len
r = qr + self.seg_len
if not self.j(self.e, l, t): return -1
left = []
right = []
while l < r:
if l & 1:left.append(l); l += 1
if r & 1:r -= 1; right.append(r)
l >>= 1; r >>= 1
ord = left + right[::-1]
now = self.e
pos = -1
for i in ord:
if self.j(now, i, t):
now = self.segf(now, self.seg[i])
else:
pos = i
break
if pos == -1:return qr
while True:
if pos >= self.seg_len:break
pos <<= 1
if self.j(now, pos, t):
now = self.segf(now, self.seg[pos])
pos += 1
return pos - self.seg_len
# -1
# (ans,qr)ans
def min_left(self,ql,qr,t):
l = ql + self.seg_len
r = qr + self.seg_len
if not self.j(self.e, r-1, t): return -1
left = []
right = []
while l < r:
if l & 1:left.append(l); l += 1
if r & 1:r -= 1; right.append(r)
l >>= 1; r >>= 1
ord = left + right[::-1]
now = self.e
pos = -1
for i in ord[::-1]:
if self.j(now, i, t):
now = self.segf(now, self.seg[i])
else:
pos = i
break
if pos == -1:return ql-1
while True:
if pos >= self.seg_len:break
pos = (pos<<1) + 1
if self.j(now, pos, t):
now = self.segf(now, self.seg[pos])
pos -= 1
return pos - self.seg_len
# ------ dual ------
def range_add(self, l, r, x):
l += self.seg_len
r += self.seg_len
while l < r:
if l & 1:
self.seg[l] = self.segf(x, self.seg[l])
l += 1
if r & 1:
r -= 1
self.seg[r] = self.segf(x, self.seg[r])
l >>= 1
r >>= 1
def get_point(self, pos):
pos += self.seg_len
res = self.seg[pos]
while True:
pos >>= 1
if not pos:
break
res = self.segf(res, self.seg[pos])
return res
def sol():
n = int(input())
p = list(map(int,input().split()))
p = [i-1 for i in p]
st = SegTree(add, [1]*n)
ans = [0]*(n)
cnt = 0
r = n-1
l = 0
for i in range(n)[::-1]:
st.point_update(p[i], 0)
sm = st.get_range(0, p[i])
bg = st.get_range(p[i], n)
cnt += min(sm, bg)
if sm < bg:
ans[i] = 0
else:
ans[i] = 1
que = deque([])
for i in range(n):
if ans[i] == 0:
que.appendleft(p[i]+1)
else:
que.append(p[i] + 1)
print(cnt)
print(*list(que))
return
T = int(input())
for i in range(T):
sol()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0