結果

問題 No.3238 Shadow
ユーザー もろこし
提出日時 2025-09-29 21:48:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 912 ms / 2,000 ms
コード長 2,836 bytes
コンパイル時間 369 ms
コンパイル使用メモリ 82,424 KB
実行使用メモリ 119,436 KB
最終ジャッジ日時 2025-09-29 21:48:39
合計ジャッジ時間 9,634 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**7)
def ii(): return int(input())
def mi(d=0): return map(lambda x:int(x)-d,input().split())
INF = float("inf")
MOD = 998244353
def answer(s):
  print(s)
  exit()
def cross(xy):
  x,y = xy
  return (x+1,y),(x-1,y),(x,y+1),(x,y-1)
################################################
class SegTree:
  def __init__(self,length,inf,order,arr=[]):
    self.inf = inf
    self.order = order
    self.bitlen = 2**length.bit_length()
    self.n = self.bitlen*2-1
    if arr:
      self.len = length
      arr += [inf]*(self.bitlen - length)
      self.arr = [None]*(self.bitlen-1) + arr
      def PreProcessing(index):
        if self.arr[index] == None:
          self.arr[index] = self.order(PreProcessing(2*index+1),PreProcessing(2*index+2))
        return self.arr[index]
      PreProcessing(0)
    else:
      self.len = 0
      self.arr = [inf]*(self.bitlen*2-1)
    self.left_index = self.bitlen-1

  #配列の末尾にxを追加。
  def Append(self,x):
    self.Renew(self.len,x)
    self.len += 1
  
  #データ更新:index番目をxに変更
  def Renew(self,index,x):
    i = self.n - self.bitlen + index
    self.arr[i] = x
    while i != 0:
      i = (i-1)//2
      result = self.order(self.arr[i*2+1],self.arr[i*2+2])
      if result != self.arr[i]:
        self.arr[i] = result
      else:
        break

  #[x,y)の範囲の結果を取得
  def GetRange(self,x,y,k=0,l=0,r=-1):
    if r == -1:
      r = self.bitlen
    if y<=l or r<=x:
      return self.inf
    elif x<=l and r<=y:
      return self.arr[k]
    else:
      return self.order(
        self.GetRange(x,y,2*k+1,l,(l+r)//2),
        self.GetRange(x,y,2*k+2,(l+r)//2,r)
        )
  
  def nibtan(self,x,k=0,left=0,right=-1,min_left=0,max_right=-1):
    if right < 0:
      right = self.bitlen
      if max_right < 0:
        max_right = self.bitlen
    if k >= self.bitlen-1:
      return k - self.bitlen+1
    else:
      center = (left+right)//2
      if center >= min_left and self.arr[2*k+1] < x:
        l = self.nibtan(x,2*k+1,left,center,min_left,max_right)
        if l >= 0: return l
      if center <= max_right and self.arr[2*k+2] < x:
        r = self.nibtan(x,2*k+2,center,right,min_left,max_right)
        if r >= 0: return r
    return -1

  def Solve(self):
    while self.left_index < self.n:
      if self.arr[self.left_index] != self.inf:
        height = self.arr[self.left_index]
        index = self.left_index - self.bitlen+1
        while 0 <= index < self.len:
          self.Renew(index,self.inf)
          index = self.nibtan(height,min_left=index)
          if index >= 0:
            height = self.arr[index + self.bitlen-1]
        print(self.left_index-self.bitlen+2,height)
      self.left_index += 1
      # print(self.arr)


n = ii()
p = list(mi())
segtree = SegTree(n,INF,min,p)
segtree.Solve()
0