結果

問題 No.3198 Monotonic Query
ユーザー dp_ijk
提出日時 2025-07-11 21:40:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 617 ms / 3,000 ms
コード長 2,550 bytes
コンパイル時間 405 ms
コンパイル使用メモリ 82,272 KB
実行使用メモリ 86,500 KB
最終ジャッジ日時 2025-07-12 10:53:14
合計ジャッジ時間 13,780 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegTree:
   def __init__(self, X_f, X_unit, seq):
      self.X_f, self.X_unit = X_f, X_unit
      if isinstance(seq, (int, float)):
         self.N = int(seq)
      else:
         seq = list(seq)
         self.N = len(seq)
      self.log = self.ceil_log2(self.N)
      self.size = 1<<self.log
      self.X = [self.X_unit] * (self.size * 2)
      if isinstance(seq, list):
         self.X[self.size:self.size + self.N] = seq
         for i in range(self.size - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i<<1], self.X[i<<1|1])

   @staticmethod
   def ceil_log2(N):
      log = 1
      while (1<<log) < N:
         log += 1
      return log

   def get(self, idx):
      assert 0 <= idx < self.N
      return self.X[idx + self.size]

   def __getitem__(self, idx: int|slice):
      if isinstance(idx, int):
         return self.get(idx)
      else:
         l = idx.start
         r = idx.stop
         if l is None: l = 0
         if r is None: r = self.N
         return self.fold(l, r)

   def set(self, idx, x):
      assert 0 <= idx < self.N
      idx += self.size
      self.X[idx] = x
      while idx > 1:
         idx >>= 1
         self.X[idx] = self.X_f(self.X[idx<<1], self.X[idx<<1|1])

   __setitem__ = set

   def fold(self, l, r):
      if l <= 0: l = 0
      if r >= self.N: r = self.N
      if l >= r: return self.X_unit
      if l == 0 and r == self.N: return self.X[1]
      if l+1 == r: return self.get(l)
      if r == self.N: r = self.size

      l += self.size
      r += self.size
      vL = self.X_unit
      vR = self.X_unit
      while l < r:
         if l&1:
            vL = self.X_f(vL, self.X[l])
            l += 1
         if r&1:
            r -= 1
            vR = self.X_f(self.X[r], vR)
         l >>= 1
         r >>= 1
      return self.X_f(vL, vR)

   def __delitem__(self, i):
      self.set(i, self.X_unit)

   def fold_all(self):
      return self.X[1]

   all_prod = prod_all = all_fold = fold_all

   def get_all(self):
      return self.X[self.size:self.size + self.N]

   def __len__(self):
      return self.N

   def __iter__(self):
      return iter(self.get_all())

   def __repr__(self):
      return repr(list(self))


   prod = fold



import typing
INF = typing.cast(int, float("INF"))

Q = int(input())
seg = SegTree(max, -INF, Q)

cnt = 0
for _ in range(Q):
   query = tuple(map(int, input().split()))
   match query:
      case 1, x:
         seg[cnt] = x
         cnt += 1
      case 2, k:
         ans = seg[cnt - k:cnt]
         print(ans)
      case _:
         assert False
0