結果

問題 No.3238 Shadow
ユーザー 👑 p-adic
提出日時 2025-08-11 20:29:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 961 ms / 2,000 ms
コード長 559 bytes
コンパイル時間 799 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 114,296 KB
最終ジャッジ日時 2025-08-15 20:50:45
合計ジャッジ時間 9,564 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

R=range
J=lambda:list(map(int,input().split()))
N,*_=J()
P=J()
p=1
while N>p:p*=2
T=[N+1]*p*2
def S(i,u):
	j=p|i
	T[j],j=u,j>>1
	while j:T[j],j=min(T[j*2],T[j*2+1]),j>>1
def G(l,r):
	l|=p
	r+=p+1
	a=b=N+1
	while l<r:
		if l&1:a,l=min(a,T[l]),l+1
		if r&1:b,r=min(T[r-1],b),r-1
		l,r=l>>1,r>>1
	return min(a,b)
o=[0]*N
for i in R(N):
	l,r=-1,N-1
	while l+1<r:
		m=(l+r)>>1
		if G(m,N-1)<P[i]:l=m
		else:r=m
	o[i]=r;S(r,min(G(r,r),P[i]))
a=[]
for i,k in zip(R(N),o):
	while k>=len(a):a+=[[N,N]]
	a[k]=[min(a[k][0],i),min(a[k][1],P[i])]
for x,y in a:print(x+1,y)
0