Submission #47798544

---

Source Code Expand

#ARC155B Abs Abs Function

'''
問題概要:
X = [A-B, A+B] から開始する。Q個のタスクを処理せよ。
・Xにa-b,a+bを追加する。
・a≦x≦b を満たすXの要素があれば、0を出力。
  そうでなければ、a,bに最も近いXの値を出力。
'''
from sortedcontainers import SortedList

#入力受取
Q,A,B=map(int,input().split())

#XをSortedListとして定義。初期値は(A-B,A+B)。
#SortedListなので重複すると困るのだが、よく考えるとべつに重複しても困らなかった。
X=SortedList([A-B,A+B])

#クエリを処理
for _ in range(Q):
    t,a,b=map(int,input().split())
    if t==1:
        #要素を追加する。SortedListなので要素が重複するが、別に困らなかった。
        X.add(a-b); X.add(a+b)
    if t==2:
        #a <= x <= b　を満たすx∈Xがあれば、0を出力。これはbisectで可能。
        Lt,Rt=X.bisect_left(a),X.bisect_right(b)
        if Rt-Lt>0: print(0)
        #そうでなければ、これらに最も近い要素を出力する。
        else:
            ans=10**18
            if Lt>0: ans=min(ans,a-X[Lt-1])
            if Rt<len(X): ans=min(ans,X[Rt]-b)
            print(ans)

Submission Info

Judge Result