結果

問題 No.3116 More and more teleporter
コンテスト
ユーザー sasa8uyauya
提出日時 2025-04-19 04:59:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,614 bytes
コンパイル時間 782 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 83,060 KB
最終ジャッジ日時 2025-04-19 05:00:16
合計ジャッジ時間 20,305 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 WA * 12 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

class BIT:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 1)

    def add(self, i, x):
        i += 1
        while i <= self.n:
            self.tree[i] += x
            i += i & -i

    def sum(self, l, r):
        if l > r or l < 0 or r >= self.n:
            return 0
        return self._prefix_sum(r) - self._prefix_sum(l - 1)

    def _prefix_sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res


n,Q=map(int,input().split())
p=[0]*(n+1)
c=BIT(n+1)
c.add(0,1)
c.add(n,1)
p[n]=n
for _ in range(Q):
  t,x,y=map(int,(input().split()+["0"])[:3])
  x-=1
  a=x
  ok=0
  ng=x+1
  while ng-ok>1:
    m=(ok+ng)//2
    if c.sum(m,x)>0:
      ok=m
    else:
      ng=m
  a=min(a,abs(x-ok)+p[ok])
  ok=n
  ng=x-1
  while ok-ng>1:
    m=(ok+ng)//2
    if c.sum(x,m)>0:
      ok=m
    else:
      ng=m
  a=min(a,abs(x-ok)+p[ok])
  if t==1:
    print(a)
  if t==2:
    if c.sum(x,x) and p[x]<=y:
      continue
    if c.sum(x,x)==0 and a<=y:
      continue
    if c.sum(x,x)==0:
      c.add(x,1)
    p[x]=y
    while 1:
      ok=0
      ng=x+1
      while ng-ok>1:
        m=(ok+ng)//2
        if c.sum(m,x)>0:
          ok=m
        else:
          ng=m
      if ok==x:
        break
      if p[ok]<=abs(x-ok)+p[x]:
        break
      c.add(ok,-1)
    while 1:
      ok=n
      ng=x-1
      while ok-ng>1:
        m=(ok+ng)//2
        if c.sum(x,m)>0:
          ok=m
        else:
          ng=m
      if ok==x:
        break
      if p[ok]<=abs(x-ok)+p[x]:
        break
      c.add(ok,-1)
0