結果

問題 No.3198 Monotonic Query
コンテスト
ユーザー もろこし
提出日時 2025-09-27 10:16:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,306 ms / 3,000 ms
コード長 1,600 bytes
コンパイル時間 364 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 87,392 KB
最終ジャッジ日時 2025-09-27 10:16:36
合計ジャッジ時間 27,041 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
sys.setrecursionlimit(10**7)
def ii(): return int(input())
def ist(): return input().split()
def mi(d=0): return map(lambda x:int(x)-d,input().split())
def lmi(d=0): return list(map(lambda x:int(x)-d,input().split()))
INF = 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,maxlen,inf,order):
    self.inf = inf
    self.order = order
    self.bitlen = 2**maxlen.bit_length()
    self.len = 0
    self.n = self.bitlen*2-1
    self.arr = [inf]*(self.bitlen*2-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
    

  #[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)
        )

q = ii()
segtree = SegTree(q,0,max)
for _ in range(q):
  query = input()
  if query[0] == "1":
    _,x = map(int,query.split())
    segtree.Append(x)
  else:
    _,k = map(int,query.split())
    print(segtree.GetRange(segtree.len-k,segtree.len))
0