Problem p03112 (python)

Fixed submission:
#       )                         .MMdMMM;                    .M#(,dM]                        .:
#       )                        .M@d@d#Mb                    dMGMM(MN                        .:
#       )                        dM1MCdbMM_                  .M@MSN;dM-                       .:
#       )                       .M#(#?d#(Mb.. ...............JMIMIMLdM]                       .:
#       )                      ..M#?NHM# ?MMMMMMMMMH"""""""HMM@(Nad#(Mb                       .:
#       )                  .(MMMMH=..-(Jg[   `               daggmp  MNm,                     .:
#       )                ..MMY`     !qN;                       (J     ?MMN,                   .:
#       )               (MMD`       .MM@                      .MM{      .WMN,                 .:
#       )              dM@`         dMM%                      .MM}        (MMm                .:
#       )             .M#`          dMN!                      .MM}        ~(MMr               .:
#       )            .MM:           dM#                       .MM}        ..JM#               .:
#       )      ``    .M@            dMF                       .MM}        .~(M#   `  .        .:
#       )      ?MMMMMMMNgJ,         .7`                        T"!       .JJjMNgNNMMMB^       .:
#       )            dMr ?Mm,                                            7YYMM#!`             .:
#       )            dMb   ?`                  .,   ` ..                 ~.(MM%               .:
#       )         ..JgMMNNN)                  .Mn.(Mm-JM{               dHHMMNag.,            .:
#       )         ("!  ?MN,..,                (NM@"`~OMM}             ..~-(M@` _?"M[          .:
#       )               ,MMM#_                .M#    .M#`           .~.~JMMMNg-..             .:
#       )           ..gMB"?TMMNJ..              `     _`         .~~.(JdM#^  _"TMMNgJ-,       .:
#       )        .gMB=`      _7WMMNaJ...                 ....__-(JJgMMMM^          ?T"^       .:
#       )           ............  ?TWMMMMNNNNgggggggggggggNNMMMMMMBY7`...                     .:
#       )           WMMMMMMMMMMMMMNgJ,   (dMMMM#"TYYYYYYMMMMMMMNgMMMMMMMMMMMNNgJ-,            .:
#       )            -?TMNmuuuuUWMMMMMMNNMM@g@MMmJ--_(JMMg@g@@gMMMMMMWUXXXUWMMMMMMNe.         .:

import sys
import bisect
input = sys.stdin.readline

a,b,q = map(int,input().split())
s = []
t = []
for i in range(a):
    S = int(input())
    s.append(S)
for i in range(b):
    T = int(input())
    t.append(T)
s.sort()
t.sort()

def f(x):
    if 0<=x and a-1>= x:
        return True
    return False
def g(x):
    if 0<=x and b-1>= x:
        return True
    return False
for i in range(q):
    x = int(input())
    p = bisect.bisect_left(s,x)
    m = bisect.bisect_left(t,x)
    
    res = []
    if f(p) and g(m):
        res.append(max(t[m],s[p])-x)
    if f(p) and g(m-1):
        res.append(min(s[p]-x,x-t[m-1])+s[p]-t[m-1])
    if f(p-1) and g(m):
        res.append(t[m]-s[p-1]+min(t[m]-x,x-s[p-1]))
    if f(p-1) and g(m-1):
        res.append(x-min(t[m-1],s[p-1]))
    print(min(res))

Buggy submission (verdict: Runtime Error):
#AVL

##search(0,x):O(logN)
# xがある場合indexを、ない場合Noneを返す
def search(root,key):
    if avl_key[root] > key:
        if avl_left[root] == None:
            return None
        else:
            return search(avl_left[root],key)
    if avl_key[root] < key:
        if avl_right[root] == None:
            return None
        else:
            return search(avl_right[root],key)
    return root


##search_lower(0,x,None):O(logN)
# xより小さいものの中で最も大きいものを出力。ない場合はNoneを出力
def search_lower(root,key,lower_key):
    if avl_key[root] > key:
        if avl_left[root] == None:
            return lower_key
        else:
            return search_lower(avl_left[root],key,lower_key)
    if avl_key[root] < key:
        lower_key = avl_key[root]
        if avl_right[root] == None:
            return lower_key
        else:
            return search_lower(avl_right[root],key,lower_key)
    
    # == 
    return key

##search_higher(0,x,None):O(logN)
# xより大きいものの中で最も小さいものを出力。ない場合はNoneを出力
def search_higher(root,key,higher_key):
    if avl_key[root] > key:
        higher_key = avl_key[root]
        if avl_left[root] == None:
            return higher_key
        else:
            return search_higher(avl_left[root],key,higher_key)
    if avl_key[root] < key:
        if avl_right[root] == None:
            return higher_key
        else:
            return search_higher(avl_right[root],key,higher_key)
    
    # == 
    return key



##Rotation,replace,insertx:insertで使用
def DoubleRightRotation(x):
    tl = avl_left[x]
    avl_left[x] = avl_right[avl_right[tl]]
    avl_right[avl_right[tl]] = x
    tlr = avl_right[tl]
    avl_right[tl] = avl_left[tlr]
    avl_left[tlr] = tl
    if balance[tlr] == -1:
        balance[avl_right[tlr]] = 1
        balance[avl_left[tlr]] = 0
    elif balance[tlr] == 1:
        balance[avl_right[tlr]] = 0
        balance[avl_left[tlr]] = -1
    else:
        balance[avl_right[tlr]] = 0
        balance[avl_left[tlr]] = 0
    balance[tlr] = 0
    return tlr

def DoubleLeftRotation(x):
    tr = avl_right[x]
    avl_right[x] = avl_left[avl_left[tr]]
    avl_left[avl_left[tr]] = x
    trl = avl_left[tl]
    avl_left[tr] = avl_right[trl]
    avl_right[trl] = tr
    if balance[trl] == 1:
        balance[avl_right[trl]] = 0
        balance[avl_left[trl]] = -1
    elif balance[trl] == -1:
        balance[avl_left[trl]] = 0
        balance[avl_right[trl]] = 1
    else:
        balance[avl_right[trl]] = 0
        balance[avl_left[trl]] = 0
    balance[trl] = 0
    return trl

def SingleLeftRotation(x):
    tr = avl_right[x]
    balance[tr] = 0
    balance[x] = 0
    avl_right[x] = avl_left[tr]
    avl_left[tr] = x
    return tr

def SingleRightRotaion(x):
    tl = avl_left[x]
    balance[tl] = 0
    balance[x] = 0
    avl_left[x] = avl_right[tl]
    avl_right[tl] = x
    return tl

def replace(x,p,v):
    if avl_left[p] == x:
        avl_left[p] = v
    else:
        avl_right[p] = v

def insertx(root,p,key):
    if avl_key[root] > key:
        if avl_left[root] == None:
            avl_key.append(key)
            avl_left[root] = len(avl_key)-1
        else:
            if not insertx(avl_left[root],root,key):
                return False
        if balance[root] == 1:
            balance[root] = 0
            return False
        elif balance[root] == 0:
            balance[root] = -1
            return True
        else:
            if balance[avl_left[root]] == 1:
                replace(root,p,DoubleRightRotation(root))
            elif balance[avl_left[root]] == -1:
                replace(root,p,SingleRightRotation(root))
            return False
    if avl_key[root] < key:
        if avl_right[root] == None:
            avl_key.append(key)
            avl_right[root] = len(avl_key)-1
        else:
            if not insertx(avl_right[root],root,key):
                return False
        if balance[root] == -1:
            balance[root] = 0
            return False
        elif balance[root] == 0:
            balance[root] = 1
            return True
        else:
            if balance[avl_right[root]] == -1:
                replace(root,p,DoubleLeftRotation(root))
            elif balance[avl_right[root]] == 1:
                replace(root,p,SingleLeftRotation(root))
            return False
    return False


##insert(0,x):O(logN)
#x追加
def insert(root,key):
    if key < avl_key[root]:
        if avl_left[root] == None:
            avl_key.append(key)
            avl_left[root] = len(avl_key)-1
        else:
            insertx(avl_left[root],root,key)
    elif key > avl_key[root]:
        if avl_right[root] == None:
            avl_key.append(key)
            avl_right[root] = len(avl_key)-1
        else:
            insertx(avl_right[root],root,key)
    else:
        pass

########################################################
##初期化（要素は一つ入れておく）

#avl_key:値,avl_left:左の子のindex,avl_right:右の子のindex
#balance[i]: {"Even":0,"Left":-1,"Right":1}

#avl_keyには初めに何か加えておく
a,b,q = map(int,input().split())
s = [int(input()) for i in range(a)]
t = [int(input()) for i in range(b)]
x = [int(input()) for i in range(q)]

avl_key = [s[0]]
avl_left = [None]*(a+2)
avl_right = [None]*(a+2)
balance = [0]*(a+2)
for i in range(1,a):
    insert(0,s[i])
insert(0,float("inf"))
insert(0,-float("inf"))

for i in range(q):
    print(search_higher(0,x[i],None))
    print(search_lower(0,x[i],None))

avl_key = [t[0]]
avl_left = [None]*b
avl_right = [None]*b
balance = [0]*b
insert(0,float("inf"))
insert(0,-float("inf"))
for i in range(1,b):
    insert(0,t[i])
for i in range(q):
    print(search_higher(0,x[i],None))
    print(search_lower(0,x[i],None))

Buggy submission (verdict: Runtime Error):
#AVL

##search(0,x):O(logN)
# xがある場合indexを、ない場合Noneを返す
def search(root,key):
    if avl_key[root] > key:
        if avl_left[root] == None:
            return None
        else:
            return search(avl_left[root],key)
    if avl_key[root] < key:
        if avl_right[root] == None:
            return None
        else:
            return search(avl_right[root],key)
    return root


##end_lower/higher:search_lower/higherで使用
def end_lower(root):
    if avl_left[root] == None:
        return avl_key[root]
    else:
        return end_lower(avl_left[root])

def end_higher(root):
    if avl_right[root] == None:
        return avl_key[root]
    else:
        return end_higher(avl_right[root])


##search_lower(0,x,None):O(logN)
# xより小さいものの中で最も大きいものを出力。ない場合はNoneを出力
def search_lower(root,key,lower_key):
    if avl_key[root] > key:
        if avl_left[root] == None:
            return lower_key
        else:
            return search_lower(avl_left[root],key,lower_key)
    if avl_key[root] < key:
        lower_key = avl_key[root]
        if avl_right[root] == None:
            return lower_key
        else:
            return search_lower(avl_right[root],key,lower_key)
    
    # == 
    if avl_left[root] == None:
        return lower_key
    else:
        if lower_key == None:
            return end_higher(avl_left[root])
        else:
            return max(lower_key,end_higher(avl_left[root]))

##search_higher(0,x,None):O(logN)
# xより大きいものの中で最も小さいものを出力。ない場合はNoneを出力
def search_higher(root,key,higher_key):
    if avl_key[root] > key:
        higher_key = avl_key[root]
        if avl_left[root] == None:
            return higher_key
        else:
            return search_higher(avl_left[root],key,higher_key)
    if avl_key[root] < key:
        if avl_right[root] == None:
            return higher_key
        else:
            return search_higher(avl_right[root],key,higher_key)
    
    # == 
    if avl_right[root] == None:
        return higher_key
    else:
        if higher_key == None:
            return end_lower(avl_right[root])
        else:
            return min(higher_key,end_lower(avl_right[root]))



##Rotation,replace,insertx:insertで使用
def DoubleRightRotation(x):
    tl = avl_left[x]
    avl_left[x] = avl_right[avl_right[tl]]
    avl_right[avl_right[tl]] = x
    tlr = avl_right[tl]
    avl_right[tl] = avl_left[tlr]
    avl_left[tlr] = tl
    if balance[tlr] == -1:
        balance[avl_right[tlr]] = 1
        balance[avl_left[tlr]] = 0
    elif balance[tlr] == 1:
        balance[avl_right[tlr]] = 0
        balance[avl_left[tlr]] = -1
    else:
        balance[avl_right[tlr]] = 0
        balance[avl_left[tlr]] = 0
    balance[tlr] = 0
    return tlr

def DoubleLeftRotation(x):
    tr = avl_right[x]
    avl_right[x] = avl_left[avl_left[tr]]
    avl_left[avl_left[tr]] = x
    trl = avl_left[tl]
    avl_left[tr] = avl_right[trl]
    avl_right[trl] = tr
    if balance[trl] == 1:
        balance[avl_right[trl]] = 0
        balance[avl_left[trl]] = -1
    elif balance[trl] == -1:
        balance[avl_left[trl]] = 0
        balance[avl_right[trl]] = 1
    else:
        balance[avl_right[trl]] = 0
        balance[avl_left[trl]] = 0
    balance[trl] = 0
    return trl

def SingleLeftRotation(x):
    tr = avl_right[x]
    balance[tr] = 0
    balance[x] = 0
    avl_right[x] = avl_left[tr]
    avl_left[tr] = x
    return tr

def SingleRightRotaion(x):
    tl = avl_left[x]
    balance[tl] = 0
    balance[x] = 0
    avl_left[x] = avl_right[tl]
    avl_right[tl] = x
    return tl

def replace(x,p,v):
    if avl_left[p] == x:
        avl_left[p] = v
    else:
        avl_right[p] = v

def insertx(root,p,key):
    if avl_key[root] > key:
        if avl_left[root] == None:
            avl_key.append(key)
            avl_left[root] = len(avl_key)-1
        else:
            if not insertx(avl_left[root],root,key):
                return False
        if balance[root] == 1:
            balance[root] = 0
            return False
        elif balance[root] == 0:
            balance[root] = -1
            return True
        else:
            if balance[avl_left[root]] == 1:
                replace(root,p,DoubleRightRotation(root))
            elif balance[avl_left[root]] == -1:
                replace(root,p,SingleRightRotation(root))
            return False
    if avl_key[root] < key:
        if avl_right[root] == None:
            avl_key.append(key)
            avl_right[root] = len(avl_key)-1
        else:
            if not insertx(avl_right[root],root,key):
                return False
        if balance[root] == -1:
            balance[root] = 0
            return False
        elif balance[root] == 0:
            balance[root] = 1
            return True
        else:
            if balance[avl_right[root]] == -1:
                replace(root,p,DoubleLeftRotation(root))
            elif balance[avl_right[root]] == 1:
                replace(root,p,SingleLeftRotation(root))
            return False
    return False


##insert(0,x):O(logN)
#x追加
def insert(root,key):
    if key < avl_key[root]:
        if avl_left[root] == None:
            avl_key.append(key)
            avl_left[root] = len(avl_key)-1
        else:
            insertx(avl_left[root],root,key)
    elif key > avl_key[root]:
        if avl_right[root] == None:
            avl_key.append(key)
            avl_right[root] = len(avl_key)-1
        else:
            insertx(avl_right[root],root,key)
    else:
        pass

########################################################
##初期化（要素は一つ入れておく）

#avl_key:値,avl_left:左の子のindex,avl_right:右の子のindex
#balance[i]: {"Even":0,"Left":-1,"Right":1}

#avl_keyには初めに何か加えておく
a,b,q = map(int,input().split())
s = [int(input()) for i in range(a)]
avl_key = [s]
avl_left = [None]*a
avl_right = [None]*a
balance = [0]*a

for i in range(1,a):
    insert(0,s[i])
t = [int(input()) for i in range(b)]
avl_key = [t[0]]
avl_left = [None]*b
avl_right = [None]*b
balance = [0]*b
for i in range(1,b):
    insert(0,t[i])

print(1)

Buggy submission (verdict: Runtime Error):
import sys
class Bintree:
    def __init__(self,data=None): # デフォルト値を使うのはrootのみ
        self.data = data
        self.left = None
        self.right = None
    def search(self,data):
        if self.data == None:
            return None
        if data < self.data:
            if self.left == None:
                return None # 左の子がなければない
            else:
                return self.left.search(data) # 左の子があれば左の子(の下を)再帰的に検索
        elif data > self.data:
            if self.right == None:
                return None
            else:
                return self.right.search(data)
        else: # data == self.dataなら発見
            return self
    
    def insert(self,data):
        if self.data == None:
            self.data = data
            return self
        if data < self.data:
            if self.left == None:
                self.left = Bintree(data) # 左の子がなければ、そこに頂点を作って登録
                return True
            else:
                return self.left.insert(data)
        elif data > self.data:
            if self.right == None:
                self.right = Bintree(data)
                return True
            else:
                return self.right.insert(data)
        else: # data == self.data:
            return False
    def to_s(self):
        return self.data
    def left_s(self):
        if self.left==None:
            return None
        return (self.left).data
    def right_s(self):
        if self.right == None:
            return None
        return (self.right).data
 
input = sys.stdin.readline
a, b, q = map(int,input().split())
s = [int(input()) for i in range(a)]
t = [int(input()) for i in range(b)]
x = [int(input()) for i in range(q)]
lens, lent = len(s), len(t)
treeA, treeB = Bintree(), Bintree()
for i in s: treeA.insert(i) # 木を作る
for i in t: treeB.insert(i)
print(1)

Buggy submission (verdict: Runtime Error):
import bisect
import sys
class Bintree:
    def __init__(self,data=None): # デフォルト値を使うのはrootのみ
        self.data = data
        self.left = None
        self.right = None
    def search(self,data):
        if self.data == None:
            return None
        if data < self.data:
            if self.left == None:
                return None # 左の子がなければない
            else:
                return self.left.search(data) # 左の子があれば左の子(の下を)再帰的に検索
        elif data > self.data:
            if self.right == None:
                return None
            else:
                return self.right.search(data)
        else: # data == self.dataなら発見
            return self
    
    def insert(self,data):
        if self.data == None:
            self.data = data
            return self
        if data < self.data:
            if self.left == None:
                self.left = Bintree(data) # 左の子がなければ、そこに頂点を作って登録
                return True
            else:
                return self.left.insert(data)
        elif data > self.data:
            if self.right == None:
                self.right = Bintree(data)
                return True
            else:
                return self.right.insert(data)
        else: # data == self.data:
            return False
    def to_s(self):
        return self.data
    def left_s(self):
        if self.left==None:
            return None
        return (self.left).data
    def right_s(self):
        if self.right == None:
            return None
        return (self.right).data

input = sys.stdin.readline
a, b, q = map(int,input().split())
s = [int(input()) for i in range(a)]
t = [int(input()) for i in range(b)]
x = [int(input()) for i in range(q)]
lens, lent = len(s), len(t)
treeA, treeB = Bintree(), Bintree()
for i in s: treeA.insert(i) # 木を作る
for i in t: treeB.insert(i)