結果

問題 No.3198 Monotonic Query
ユーザー moon17
提出日時 2025-07-11 21:34:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 339 ms / 3,000 ms
コード長 1,548 bytes
コンパイル時間 398 ms
コンパイル使用メモリ 82,104 KB
実行使用メモリ 113,212 KB
最終ジャッジ日時 2025-07-12 10:51:43
合計ジャッジ時間 8,781 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

class segtree():
 n=size=1;d,op,e=[0],None,10**15
 def __init__(self,V,OP,E):
  self.n=len(V);self.op=OP;self.e=E;self.size=1<<(self.n-1).bit_length();self.d=[E]*2*self.size
  for i in range(self.n):self.d[self.size+i]=V[i]
  for i in range(self.size)[::-1]:self.update(i)
 def __setitem__(self,p,x):
  p+=self.size;self.d[p]=x
  while p:p>>=1;self.update(p)
 def __getitem__(self,p):return self.d[p+self.size]
 def prod(self,l,r):
  sml=smr=self.e;l+=self.size;r+=self.size
  while l<r:
   if l&1:sml=self.op(sml,self.d[l]);l+=1
   if r&1:r-=1;smr=self.op(self.d[r],smr)
   l>>=1;r>>=1
  return self.op(sml,smr)
 def all_prod(self):return self.d[1]
 def max_right(self,l,f):
  if l==self.n:return self.n
  l+=self.size;sm=self.e
  while 1:
   while l%2==0:l>>=1
   if not f(self.op(sm,self.d[l])):
    while l<self.size:
     l=2*l
     if f(self.op(sm,self.d[l])):sm=self.op(sm,self.d[l]);l+=1
    return l-self.size
   sm=self.op(sm,self.d[l]);l+=1
   if (l&-l)==l:break
  return self.n
 def min_left(self,r,f):
  if r==0:return 0
  r+=self.size;sm=self.e
  while 1:
   r-=1
   while r>1 and r%2:r>>=1
   if not f(self.op(self.d[r],sm)):
    while r<self.size:
     r=2*r+1
     if f(self.op(self.d[r],sm)):sm=self.op(self.d[r],sm);r-=1
    return r+1-self.size
   sm=self.op(self.d[r],sm)
   if (r&-r)==r:break
  return 0
 def update(self,k):self.d[k]=self.op(self.d[2*k],self.d[2*k+1])
(q,),*e=[[*map(int,s.split())]for s in open(0)]
a=segtree([0]*q,max,0)
l=0
for z,x in e:
  if z==1:
    a[l]=x
    l+=1
  else:
    print(a.prod(l-x,l))
0