結果

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

ソースコード

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