Problem: Along a road running in an east-west direction, there are A shrines and B temples. The i-th shrine from the west is located at a distance of s_i meters from the west end of the road, and the i-th temple from the west is located at a distance of t_i meters from the west end of the road.  Answer the following Q queries:    * Query i (1 \leq i \leq Q): If we start from a point at a distance of x_i meters from the west end of the road and freely travel along the road, what is the minimum distance that needs to be traveled in order to visit one shrine and one temple? (It is allowed to pass by more shrines and temples than required.)

Submission attempts (in order):
def search(x,r):
  low = 0
  high = len(r)-1
  mid = (low+high)//2
  while low<=high:
    rr = r[mid]-x
    ll = r[mid+1]-x
    if rr*ll<=0:
      return(abs(rr),abs(ll))
    elif r[mid]-x > 0:
      high = mid
      mid = (low+high)//2
    else:
      low = mid
      mid = (low+high)//2
      

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

for xx in x:

  s_l = float('inf')
  s_r = float('inf')
  if s[-1] - xx <= 0:
    s_l = abs(s[-1] - xx)
  elif s[0] - xx >= 0:
    s_r = abs(s[0] - xx)
  else:
  	s_l,s_r=search(xx,s)
  
  t_l = float('inf')
  t_r = float('inf')
  if t[-1] - xx <= 0:
    t_l = abs(t[-1] - xx)
  elif t[0] - xx >= 0:
    t_r = abs(t[0] - xx)
  else:
  	t_l,t_r=search(xx,t)
  
  #print(s_l,s_r,t_l,t_r)
  
  #l = max(s_l,t_l)
  #r = max(s_r,t_r)
  if s_l <= t_l:
    l = t_l
    lr = s_l*2 + t_r
  else:
    r = s_l
    lr = t_l*2 + s_r
  if s_r <= t_r:
    r = t_r
    rl = s_r*2 + t_l
  else:
    r = s_r
    lr = t_r*2 + s_l
 
  ans = min(l,r,lr,rl)
  print(ans)
  

def search(x,r):
  low = 0
  high = len(r)-1
  mid = (low+high)//2
  while low<=high:
    rr = r[mid]-x
    ll = r[mid+1]-x
    if rr*ll<=0:
      return(abs(rr),abs(ll))
    elif r[mid]-x > 0:
      high = mid
      mid = (low+high)//2
    else:
      low = mid
      mid = (low+high)//2
      

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

for xx in x:

  s_l = float('inf')
  s_r = float('inf')
  if s[-1] - xx <= 0:
    s_l = abs(s[-1] - xx)
  elif s[0] - xx >= 0:
    s_r = abs(s[0] - xx)
  else:
  	s_l,s_r=search(xx,s)
  
  t_l = float('inf')
  t_r = float('inf')
  if t[-1] - xx <= 0:
    t_l = abs(t[-1] - xx)
  elif t[0] - xx >= 0:
    t_r = abs(t[0] - xx)
  else:
  	t_l,t_r=search(xx,t)
  
  #print(s_l,s_r,t_l,t_r)
  
  #l = max(s_l,t_l)
  #r = max(s_r,t_r)
  if s_l <= t_l:
    l = t_l
    lr = s_l*2 + t_r
  else:
    r = s_l
    lr = t_l*2 + s_r
  if s_r <= t_r:
    r = t_r
    rl = s_r*2 + t_l
  else:
    r = s_r
    rl = t_r*2 + s_l
 
  ans = min(l,r,lr,rl)
  print(ans)
  

def search(x,r):
  low = 0
  high = len(r) - 1
  while low < high:
    mid = (low+high)//2
    if x < r[mid]:
      high = mid
    else:
      low = mid + 1
  return(abs(r[low-1]-x),abs(r[low]-x))
      
a, b, q = [int(i) for i in input().split()]
s = [-float('inf')] + [int(input()) for _ in range(a)] + [float('inf')]
t = [-float('inf')] + [int(input()) for _ in range(b)] + [float('inf')]
x = [int(input()) for _ in range(q)]

for xx in x:
  
  s_l,s_r=search(xx,s)
  t_l,t_r=search(xx,t)
  
  if s_l <= t_l:
    l = t_l
    lr = s_l*2 + t_r
  else:
    l = s_l
    lr = t_l*2 + s_r
  if s_r <= t_r:
    r = t_r
    rl = s_r*2 + t_l
  else:
    r = s_r
    rl = t_r*2 + s_l
 
  ans = min(l,r,lr,rl)
  print(ans)
  

Verdicts: Runtime Error

Runtime Error

Accepted