結果

問題 No.3116 More and more teleporter
ユーザー sasa8uyauya
提出日時 2025-04-19 04:56:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,978 bytes
コンパイル時間 225 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 83,932 KB
最終ジャッジ日時 2025-04-19 04:56:39
合計ジャッジ時間 21,030 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 12
権限があれば一括ダウンロードができます

ソースコード

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
  if t==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])
    print(a)
  if t==2:
    if c.sum(x,x) and p[x]<=y:
      continue
    if c.sum(x,x)==0:
      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 a<=y:
        continue
    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