結果
問題 |
No.3198 Monotonic Query
|
ユーザー |
👑 ![]() |
提出日時 | 2025-07-12 03:19:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 528 ms / 3,000 ms |
コード長 | 1,154 bytes |
コンパイル時間 | 269 ms |
コンパイル使用メモリ | 82,772 KB |
実行使用メモリ | 82,900 KB |
最終ジャッジ日時 | 2025-07-12 10:56:42 |
合計ジャッジ時間 | 12,162 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#0-indexed , 半開区間[a,b) #calc変更で演算変更 class SegTree: def __init__(self,N,first): self.NO = 2**(N-1).bit_length() self.First = first self.data = [first] * (2*self.NO) def calc(self,l,r): return max(l,r) def update(self,ind,x): ind += self.NO - 1 self.data[ind] = x while ind >= 0: ind = (ind - 1)//2 self.data[ind] = self.calc(self.data[2*ind+1],self.data[2*ind+2]) def query(self,l,r): L = l + self.NO R = r + self.NO s = self.First while L < R: if R & 1: R -= 1 s = self.calc(s , self.data[R-1]) if L & 1: s = self.calc(s , self.data[L-1]) L += 1 L >>= 1 R >>= 1 return s def get(self , ind): ind += self.NO - 1 return self.data[ind] Q = int(input()) seg = SegTree(Q+10,0) cnt = 0 ANS = [] for _ in range(Q): ty,x = map(int,input().split()) if ty == 1: seg.update(cnt,x) cnt += 1 else: print ( seg.query(cnt-x,cnt) )