Submission #47798507

---

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を使うが、要素の重複には十分注意すること。
#重複対策としては N not in X: X.add(N) としたり、先にX.discard(N)をしたりする方法がある。
X=SortedList([A-B])
X.discard(A+B); X.add(A+B)

#クエリを処理
for _ in range(Q):
    t,a,b=map(int,input().split())
    if t==1:
        #要素を追加する。SortedListなので要素の重複に注意。
        X.discard(a-b); X.add(a-b)
        X.discard(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