結果
| 問題 |
No.3167 [Cherry 7th Tune C] Cut in Queue
|
| ユーザー |
👑  Kazun
|
| 提出日時 | 2024-02-07 23:22:01 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 816 ms / 2,500 ms |
| コード長 | 7,593 bytes |
| コンパイル時間 | 359 ms |
| コンパイル使用メモリ | 82,224 KB |
| 実行使用メモリ | 192,328 KB |
| 最終ジャッジ日時 | 2025-05-30 21:03:18 |
| 合計ジャッジ時間 | 28,391 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 43 |
ソースコード
class Doubly_Linked_List:
def __init__(self, N):
self.__N=N
self.__front=[-1]*N
self.__back=[-1]*N
def __len__(self):
return self.__N
def __str__(self):
res=[]
used=[0]*self.__N
for x in range(self.__N):
if used[x]:
continue
a=self.enumerate(x)
for y in a:
used[y]=1
res.append(a)
return str(res)
def __repr__(self):
return "[Doubly Linked List]: "+str(self)
def previous(self, x, default=-1):
return self.__front[x] if self.__front[x]!=-1 else default
def next(self, x, default=-1):
return self.__back[x] if self.__back[x]!=-1 else default
def disconnect_front(self, x):
""" x から前に伸びるリンクを削除する.
"""
front=self.__front; back=self.__back
y=front[x]
if y>=0:
front[x]=-1
back[y]=-1
def disconnect_back(self, x):
""" x から後ろに伸びるリンクを削除する.
"""
front=self.__front; back=self.__back
y=back[x]
if y>=0:
back[x]=-1
front[y]=-1
def extract(self, x):
""" x に接続するリンクを削除し, x の前後が存在するならば, それらをつなぐ.
"""
a=self.__front[x]
b=self.__back[x]
self.disconnect_front(x)
self.disconnect_back(x)
if a!=-1 and b!=-1:
self.connect(a,b)
def connect(self, x, y):
""" x から y へのリンクを生成する (すでにある x からのリンクと y へのリンクは削除される).
"""
self.disconnect_back(x)
self.disconnect_front(y)
self.__back[x]=y
self.__front[y]=x
def insert_front(self, x, y):
""" x の前に y を挿入する.
"""
z=self.__front[x]
self.connect(y,x)
if z!=-1:
self.connect(z,y)
def insert_back(self, x, y):
""" x の後に y を挿入する.
"""
z=self.__back[x]
self.connect(x,y)
if z!=-1:
self.connect(y,z)
def head(self, x):
""" x が属する弱連結成分の先頭を求める.
"""
while self.__front[x]!=-1:
x=self.__front[x]
return x
def tail(self, x):
""" x が属する弱連結成分の末尾を求める.
"""
while self.__back[x]!=-1:
x=self.__back[x]
return x
def enumerate(self, x):
""" x が属している弱連結成分を先頭から順に出力する.
"""
x=self.head(x)
res=[x]
while self.__back[x]>=0:
x=self.__back[x]
res.append(x)
return res
def depth(self, x):
dep=0
while self.__front[x]!=-1:
x=self.__front[x]
dep+=1
return dep
class Binary_Indexed_Tree():
def __init__(self, L, op, zero, neg):
""" op を演算とする N 項の Binary Indexed Tree を作成
op: 演算 (2変数関数, 可換群)
zero: 群 op の単位元 (x+e=e+x=x を満たす e)
neg : 群 op の逆元 (1変数関数, x+neg(x)=neg(x)+x=e をみたす neg(x))
"""
self.op=op
self.zero=zero
self.neg=neg
self.N=N=len(L)
self.log=N.bit_length()-1
X=[zero]*(N+1)
for i in range(N):
p=i+1
X[p]=op(X[p],L[i])
q=p+(p&(-p))
if q<=N:
X[q]=op(X[q], X[p])
self.data=X
def get(self, k):
""" 第 k 要素の値を出力する.
k : 数列の要素
index: 先頭の要素の番号
"""
return self.sum(k, k)
def add(self, k, x):
""" 第 k 要素に x を加え, 更新を行う.
k : 数列の要素
x : 加える値
"""
data=self.data; op=self.op
p=k+1
while p<=self.N:
data[p]=op(self.data[p], x)
p+=p&(-p)
def update(self, k, x):
""" 第 k 要素を x に変え, 更新を行う.
k: 数列の要素
x: 更新後の値
"""
a=self.get(k)
y=self.op(self.neg(a), x)
self.add(k,y)
def sum(self, l, r):
""" 第 l 要素から第 r 要素までの総和を求める.
※ l != 0 を使うならば, 群でなくてはならない.
l: 始まり
r: 終わり
"""
l=l+1 if 0<=l else 1
r=r+1 if r<self.N else self.N
if l>r:
return self.zero
elif l==1:
return self.__section(r)
else:
return self.op(self.neg(self.__section(l-1)), self.__section(r))
def __section(self, x):
""" B[0]+...+B[x] を求める. """
data=self.data; op=self.op
S=self.zero
while x>0:
S=op(data[x], S)
x-=x&(-x)
return S
def all_sum(self):
return self.sum(0, self.N-1)
def binary_search(self, cond):
""" cond(B[0]+...+B[k]) が True となるような最小の k を返す.
cond: 単調増加
※ cond(zero)=True の場合の返り値は -1 とする.
※ cond(B[0]+...+B[k]) なる k が (0<=k<N に) 存在しない場合の返り値は N とする.
"""
if cond(self.zero):
return -1
j=0
r=self.N
t=1<<self.log
data=self.data; op=self.op
alpha=self.zero
while t>0:
if j+t<=self.N:
beta=op(alpha, data[j+t])
if not cond(beta):
alpha=beta
j+=t
t>>=1
return j
def __getitem__(self, index):
if isinstance(index, int):
return self.get(index)
else:
return [self.get(t) for t in index]
def __setitem__(self, index, val):
self.update(index, val)
def __iter__(self):
for k in range(self.N):
yield self.sum(k, k)
#==================================================
def solve():
from operator import add, neg
N = int(input())
A = [-1] + list(map(int, input().split()))
Q = int(input())
last = N + Q + 1
L = Doubly_Linked_List(N + Q + 2)
for i in range(1, N):
L.connect(A[i], A[i + 1])
L.connect(0, A[1])
L.connect(A[N], last)
queries = [None] * Q
b = N + 1
for q in range(Q):
t, *val = map(int, input().split())
if t == 1:
a, = val
if a == 0:
a = last
p = L.previous(a)
L.connect(p, b)
L.connect(b, a)
b += 1
queries[q] = (t, *val)
X = list(L.enumerate(0))
X_inv = [-1] * (N + Q + 2)
for i, x in enumerate(X):
X_inv[x] = i
BIT = Binary_Indexed_Tree([1 if 1 <= x <= N else 0 for x in X], add, 0, neg)
ans = []
b = N + 1
for query in queries:
t, *val = query
if t == 1:
BIT.update(X_inv[b], 1)
b += 1
elif t == 2:
j = BIT.binary_search(lambda x: x > 0)
BIT.update(j, 0)
else:
k, = val
ans.append(X[BIT.binary_search(lambda c: c >= k)])
return ans
#==================================================
import sys
input = sys.stdin.readline
write = sys.stdout.write
write("\n".join(map(str, solve())))