結果

問題 No.3116 More and more teleporter
ユーザー moon17
提出日時 2025-04-19 18:33:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 427 ms / 2,000 ms
コード長 2,099 bytes
コンパイル時間 533 ms
コンパイル使用メモリ 82,968 KB
実行使用メモリ 113,564 KB
最終ジャッジ日時 2025-04-19 18:33:32
合計ジャッジ時間 7,251 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

class segtree():
 n,size,log,d,op,e=1,1,2,[0],None,10**15
 def __init__(self,V,OP,E):
  self.n=len(V);self.op=OP;self.e=E
  self.log=(self.n-1).bit_length()
  self.size=1<<self.log
  self.d=[E for i in range(2*self.size)]
  for i in range(self.n):self.d[self.size+i]=V[i]
  for i in range(self.size-1,0,-1):self.update(i)
 def set(self,p,x):
  assert 0<=p and p<self.n
  p+=self.size;self.d[p]=x
  for i in range(1,self.log+1):self.update(p>>i)
 def get(self,p):
  assert 0<=p and p<self.n
  return self.d[p+self.size]
 def prod(self,l,r):
  assert 0<=l and l<=r and r<=self.n
  sml,smr=self.e,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:smr=self.op(self.d[r-1],smr);r-=1
   l>>=1
   r>>=1
  return self.op(sml,smr)
 def all_prod(self):
  return self.d[1]
 def max_right(self,l,f):
  assert 0<=l and l<=self.n
  assert f(self.e)
  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):
  assert 0<=r and r<=self.n
  assert f(self.e)
  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])
 def __str__(self):
  return str([self.get(i) for i in range(self.n)])
(n,q),*e=[[*map(int,s.split())]for s in open(0)]
INF=1<<60
r=segtree([0]*n,min,INF)
l=segtree([i*2 for i in range(n)],min,INF)
for k,x,*c in e:
  # print([r.get(i)for i in range(n)],[l.get(i)for i in range(n)])
  x-=1
  if k==1:
    mr=r.prod(0,x)+x
    ml=l.prod(x,n)-x
    print(min(mr,ml))
  else:
    c=c[0]
    r.set(x,min(r.get(x),c-x))
    l.set(x,min(l.get(x),c+x))
0