Problem:


Score : 400 points

Problem Statement

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.)

Constraints

1 \leq A, B \leq 10^5

1 \leq Q \leq 10^5

1 \leq s_1 < s_2 < ... < s_A \leq 10^{10}

1 \leq t_1 < t_2 < ... < t_B \leq 10^{10}

1 \leq x_i \leq 10^{10}

s_1, ..., s_A, t_1, ..., t_B, x_1, ..., x_Q are all different.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B Q
s_1
:
s_A
t_1
:
t_B
x_1
:
x_Q

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

2 3 4
100
600
400
900
1000
150
2000
899
799

Sample Output 1

350
1400
301
399

There are two shrines and three temples. The shrines are located at distances of 100, 600 meters from the west end of the road, and the temples are located at distances of 400, 900, 1000 meters from the west end of the road.

Query 1: If we start from a point at a distance of 150 meters from the west end of the road, the optimal move is first to walk 50 meters west to visit a shrine, then to walk 300 meters east to visit a temple.

Query 2: If we start from a point at a distance of 2000 meters from the west end of the road, the optimal move is first to walk 1000 meters west to visit a temple, then to walk 400 meters west to visit a shrine. We will pass by another temple on the way, but it is fine.

Query 3: If we start from a point at a distance of 899 meters from the west end of the road, the optimal move is first to walk 1 meter east to visit a temple, then to walk 300 meters west to visit a shrine.

Query 4: If we start from a point at a distance of 799 meters from the west end of the road, the optimal move is first to walk 199 meters west to visit a shrine, then to walk 200 meters west to visit a temple.

Sample Input 2

1 1 3
1
10000000000
2
9999999999
5000000000

Sample Output 2

10000000000
10000000000
14999999998

The road is quite long, and we may need to travel a distance that does not fit into a 32-bit integer.



Sample input:
2 3 4
100
600
400
900
1000
150
2000
899
799


Sample output:
350
1400
301
399

Submission status: Time Limit Exceeded

Solution code:
import bisect

A, B, Q = map(int, input().split())
s = [0]*(A+4)
t = [0]*(B+4)

for i in range(2, A+2):
    s[i] = int(input())

for i in range(2, B+2):
    t[i] = int(input())

s[0], s[1], s[-2], s[-1] = -10**11-1, -10**11, 10**11, 10**11+1
t[0], t[1], t[-2], t[-1] = -10**11-1, -10**11, 10**11, 10**11+1


for i in range(Q):
    x = int(input())
    sh_left = bisect.bisect(s, x) - 1
    sh_right = bisect.bisect(s, x)
    ans = 10**12
    for i in range(2):
        loc_sh = s[[sh_left, sh_right][i]]
        dis = abs(x-loc_sh)
        te_left = bisect.bisect(t, loc_sh) - 1
        te_right = bisect.bisect(t, loc_sh)
        loc_te_l = t[te_left]
        loc_te_r = t[te_right]
        tmp = min(dis+abs(loc_sh-loc_te_l), dis+abs(loc_sh-loc_te_r))
        ans = min(ans, tmp)
    te_left = bisect.bisect(t, x) - 1
    te_right = bisect.bisect(t, x)
    for i in range(2):
        loc_te = t[[te_left, te_right][i]]
        dis = abs(x-loc_te)
        sh_left = bisect.bisect(s, loc_te) - 1
        sh_right = bisect.bisect(s, loc_te)
        loc_sh_l = s[sh_left]
        loc_sh_r = s[sh_right]
        tmp = min(dis+abs(loc_te-loc_sh_l), dis+abs(loc_te-loc_sh_r))
        ans = min(ans, tmp)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

A, B, Q = map(int, input().split())
s = [0]*(A+4)
t = [0]*(B+4)

for i in range(2, A+2):
    s[i] = int(input())

for i in range(2, B+2):
    t[i] = int(input())

s[0], s[1], s[-2], s[-1] = -10**11-1, -10**11, 10**11, 10**11+1
t[0], t[1], t[-2], t[-1] = -10**11-1, -10**11, 10**11, 10**11+1


for i in range(Q):
    ans = 10**11
    x = int(input())
    sh_left = bisect.bisect(s, x) - 1
    sh_right = bisect.bisect(s, x)
    for i in range(2):
        loc_sh = s[[sh_left, sh_right][i]]
        te_left = bisect.bisect(t, loc_sh) - 1
        te_right = bisect.bisect(t, loc_sh)
        loc_te_l = t[te_left]
        loc_te_r = t[te_right]
        ans = min(ans, min(abs(x-loc_sh)+abs(loc_sh-loc_te_l), abs(x-loc_sh)+abs(loc_sh-loc_te_r)))
    te_left = bisect.bisect(t, x) - 1
    te_right = bisect.bisect(t, x)
    for i in range(2):
        loc_te = t[[te_left, te_right][i]]
        sh_left = bisect.bisect(s, loc_te) - 1
        sh_right = bisect.bisect(s, loc_te)
        loc_sh_l = s[sh_left]
        loc_sh_r = s[sh_right]
        ans = min(ans, min(abs(x-loc_te)+abs(loc_te-loc_sh_l), abs(x-loc_te)+abs(loc_te-loc_sh_r)))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
A, B, Q = [int(a) for a in input().split(" ")]
S = sorted([int(input()) for i in range(A)])
T = sorted([int(input()) for i in range(B)])
X = [int(input()) for i in range(Q)]
INF = float("inf")

def search(arr, x):
    l, r = (0, len(arr))
    while r-l>1:
        med = (l+r)//2
        if arr[med] == x:
            return med
        l, r = (l, med) if x<arr[med] else (med+1, r)
    return l

for x in X:
    s1 = min(search(S, x), len(S)-1)
    t1 = min(search(T, x), len(T)-1)
    ss, ts = None, None
    
    if S[s1]==x:
        ss = (0, 0)
    elif s1==0 and x<S[s1]:
        ss = (INF, abs(S[s1]-x))
    elif s1==len(S)-1 and S[s1]<x:
        ss = (abs(S[s1]-x), INF)
    elif S[s1]<x:
        ss = (abs(S[s1]-x), abs(S[s1+1]-x))
    else:
        ss = (abs(S[s1-1]-x), abs(S[s1]-x))
    
    if T[t1]==x:
        ts = (0, 0)
    elif t1==0 and x<T[t1]:
        ts = (INF, abs(T[t1]-x))
    elif t1==len(T)-1 and T[t1]<x:
        ts = (abs(T[t1]-x), INF)
    elif T[t1]<x:
        ts = (abs(T[t1]-x), abs(T[t1+1]-x))
    else:
        ts = (abs(T[t1-1]-x), abs(T[t1]-x))

    ans = min([max(ss[0], ts[0]), max(ss[1], ts[1]),
               2*ss[0]+ts[1], 2*ss[1]+ts[0], ss[0]+2*ts[1], ss[1]+2*ts[0]])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)]


def binary_search(list, a):
    r = 0
    l = len(list)-1
    while l - r > 1:
        if list[(r+l)//2] > a:
            l = (r+l)//2
        else:
            r = (r+l)//2
    return r, l


def cost(start, s, t):
    if s == t:
        return abs(start - s)

    min_o = min(s, t)
    max_o = max(s, t)
    if start <= min_o:
        return max_o - start
    elif start <= max_o:
        return min(abs(start-min_o), abs(start-max_o)) + (max_o-min_o)
    else:
        return start - min_o


for start in x:
    s_r, s_l = binary_search(s, start)
    s_r_t_r, s_r_t_l = binary_search(t, s[s_r])
    s_l_t_r, s_l_t_l = binary_search(t, s[s_l])

    res0 = cost(start, s[s_r], t[s_r_t_r])
    res1 = cost(start, s[s_r], t[s_r_t_l])
    res2 = cost(start, s[s_l], t[s_l_t_r])
    res3 = cost(start, s[s_l], t[s_l_t_l])
    print(min(res0, res1, res2, res3))

Submission status: Time Limit Exceeded

Solution code:
A,B,Q=[int(i) for i in input().split()]
s=[]
t=[]
x=[]
for i in range(A):
	s.append(int(input()))
for i in range(B):
	t.append(int(input()))
for i in range(Q):
	x.append(int(input()))

def sloc(a):
	for i in range(A-1):
		if abs(s[i]-a)>abs(s[i+1]-a):
			continue
		else:
			return s[i]
	return s[A-1]
def tloc(a):
	for i in range(B-1):
		if abs(t[i]-a)>abs(t[i+1]-a):
			continue
		else:
			return t[i]
	return t[B-1]
for xx in x:
	a=sloc(xx)
	b=tloc(a)
	ss=abs(a-xx)+abs(a-b)
	c=tloc(xx)
	d=sloc(c)
	tt=abs(c-xx)+abs(c-d)
	print(min(ss,tt))

Submission status: Time Limit Exceeded

Solution code:
A,B,Q = map(int,input().split())
Ss = []
for i in range(A):
    Ss.append(int(input()))
Ts = []
for i in range(B):
    Ts.append(int(input()))

def binary_search(search_list,target):
    left = 0
    right = len(search_list)
    while left < right:
        center = (left + right)//2
        if search_list[center] < target:
            left = center + 1
        elif search_list[center] > target:
            right = center
    index = left
    return index-1

S_to_T = []
for i in range(A):
    index = binary_search(Ts,Ss[i])
    if index+1 == B:
        right = float('inf')
    else:
        right = abs(Ss[i]-Ts[index+1])
    length = min(abs(Ss[i]-Ts[index]),right)
    S_to_T.append(length)
T_to_S = []
for i in range(B):
    index = binary_search(Ss,Ts[i])
    if index+1 == A:
        right = float('inf')
    else:
        right = abs(Ts[i]-Ss[index+1])
    length = min(abs(Ts[i]-Ss[index]),right)
    T_to_S.append(length)

for i in range(Q):
    q = int(input())
    Sindex = binary_search(Ss,q)
    S_left = abs(Ss[Sindex]-q)+S_to_T[Sindex]
    if Sindex+1 == A:
        S_right = float('inf')
    else:
        S_right = abs(Ss[Sindex+1]-q)+S_to_T[Sindex+1]
    Tindex = binary_search(Ts,q)
    T_left = abs(Ts[Tindex]-q)+T_to_S[Tindex]
    if Tindex+1 == B:
        T_right = float('inf')
    else:
        T_right = abs(Ts[Tindex+1]-q)+T_to_S[Tindex+1]
    ans = min(S_left,S_right,T_left,T_right)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
A,B,Q = list(map(int,input().split())) 
S = [int(input()) for _ in range(A) ]
T = [int(input()) for _ in range(B) ]
x = [int(input()) for _ in range(Q)]
#S = np.array(S)
#T = np.array(T)
for a in x:
    ans1 = 0
    ans2 = 0
    S1 = list(map(lambda x : abs(x-a),S))
    T1 = list(map(lambda x: abs(x-a),T))
    ans1 +=min(T1)
    ans1 += min(map(lambda x:abs(x-T[T1.index(min(T1))]),S))
    ans2+=min(S1)
    ans2+= min(map(lambda x:abs(x-S[S1.index(min(S1))]),T))
    print(min(ans1,ans2))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
A,B,Q = list(map(int,input().split())) 
S = [int(input()) for _ in range(A) ]
T = [int(input()) for _ in range(B) ]
x = [int(input()) for _ in range(Q)]
#S = np.array(S)
#T = np.array(T)
for a in x:
    ans1 = 0
    ans2 = 0
    S1 = list(map(lambda x : abs(x-a),S))
    T1 = list(map(lambda x: abs(x-a),T))
    ans1 +=min(T1)
    ans1 += min(map(lambda x:abs(x-T[T1.index(min(T1))]),S))
    ans2+=min(S1)
    ans2+= min(map(lambda x:abs(x-S[S1.index(min(S1))]),T))
    print(min(ans1,ans2))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
A,B,Q=map(int, input().split())
s=[int(input()) for _ in range(A)] + [10**11]
t=[int(input()) for _ in range(B)] + [10**11]
for _ in range(Q):
	x = int(input())
	ans = []
	ps = bisect(s, x)
	pt = bisect(t, x)
	for vs in (s[ps], s[ps-1]):
		for vt in (t[pt], t[pt-1]):
			ans.append(abs(x - vs) + abs(vs - vt))
			ans.append(abs(x - vt) + abs(vt - vs))
	print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
A,B,Q=map(int, input().split())
s=[int(input()) for _ in range(A)] + [99**99]
t=[int(input()) for _ in range(B)] + [99**99]
for _ in range(Q):
	x = int(input())
	ans = []
	ps = bisect(s, x)
	pt = bisect(t, x)
	for vs in (s[ps], s[ps-1]):
		for vt in (t[pt], t[pt-1]):
			ans.append(abs(x - vs) + abs(vs - vt))
			ans.append(abs(x - vt) + abs(vt - vs))
	print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
A,B,Q = list(map(int,input().split())) 
S = [int(input()) for _ in range(A) ]
T = [int(input()) for _ in range(B) ]
x = [int(input()) for _ in range(Q)]
S = np.array(S)
T = np.array(T)
for a in x:
    ans1 = 0
    ans2 = 0
    S1 = abs(S-a)
    T1 = abs(T-a)
    ans1 +=np.min(T1)
    ans1 += np.min(abs(S-T[np.argmin(T1)]))
    ans2+=np.min(S1)
    ans2+= np.min(abs(T-S[np.argmin(S1)]))
    print(min(ans1,ans2))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
A,B,Q = list(map(int,input().split())) 
S = [int(input()) for _ in range(A) ]
T = [int(input()) for _ in range(B) ]
x = [int(input()) for _ in range(Q)]
S = np.array(S)
T = np.array(T)
for a in x:
    ans1 = 0
    ans2 = 0
    S1 = abs(S-a)
    T1 = abs(T-a)
    ans1 +=np.min(T1)
    ans1 += min(abs(S-T[np.argmin(T1)]))
    ans2+=np.min(S1)
    ans2+= min(abs(T-S[np.argmin(S1)]))
    print(min(ans1,ans2))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
A,B,Q=map(int, input().split())
s=[int(input()) for _ in range(A)] + [99**99]
t=[int(input()) for _ in range(B)] + [99**99]
snt=[0]*A + [99**99]
tns=[0]*B + [99**99]
for i in range(A):
	p = bisect(t, s[i])
	snt[i] = min(abs(s[i] - t[p-1]), abs(s[i] - t[p]))
for i in range(B):
	p = bisect(s, t[i])
	tns[i] = min(abs(t[i] - s[p-1]), abs(t[i] - s[p]))
for _ in range(Q):
	x = int(input())
	ans = []
	p = bisect(s, x)
	ans.append(abs(s[p] - x) + snt[p])
	ans.append(abs(s[p-1] - x) + snt[p-1])
	p = bisect(t, x)
	ans.append(abs(t[p] - x) + tns[p])
	ans.append(abs(t[p-1] - x) + tns[p-1])
	print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
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)]

def search(a):
  cur = a
  sx, tx = [], [] #xiとsi、tiの差のリスト
  for si in s:
    sx.append(abs(si - a))
  for ti in t:
    tx.append(abs(ti - a))
  stmin = [[sx.index(min(sx)),min(sx)], [tx.index(min(tx)),min(tx)]]
  ans = min(stmin[0][1], stmin[1][1])
  
#  if stmin[0][1] <= stmin[1][1]: #sのほうが近いとき
  cur1 = s[stmin[0][0]]
  tcur = []
  for ti in t:
    tcur.append(abs(ti - cur1))
  ans1 = stmin[0][1] + min(tcur)
    
#  if stmin[0][1] > stmin[1][1]: #tのほうが近いとき
  cur2 = t[stmin[1][0]]
  scur = []
  for si in s:
    scur.append(abs(si - cur2))
  ans2 = stmin[1][1] + min(scur)
  
  print(min(ans1, ans2))
  
for xi in x:
  search(xi)

Submission status: Time Limit Exceeded

Solution code:
import math

A,B,Q = map(int, input().split())
S=[0]*A
T=[0]*B
for i in range(A):
  S[i] = int(input())
for i in range(B):
  T[i] = int(input())
S.append(10**11)
S.insert(0,(-1)*(10**11))
T.append(10**11)
T.insert(0,(-1)*(10**11))
for i in range(Q):
  x = int(input())
  floor = 0
  ceil = len(S)-1
  while ceil-floor > 1:
    half = math.floor((floor+ceil)/2)
    s = S[half]
    if s < x:
      floor = half
    else:
      ceil = half
  nearest_x_S = [S[floor]-x, S[ceil]-x]
        
  floor = 0
  ceil = len(T)-1
  while ceil-floor > 1:
    half = math.floor((floor+ceil)/2)
    t = T[half]
    if t < x:
      floor = half
    else:
      ceil = half
  nearest_x_T = [T[floor]-x, T[ceil]-x]
  
  ans_cand = []
  for x_S in nearest_x_S:
    for x_T in nearest_x_T:
      if x_S*x_T > 0:
        ans_cand.append(max(abs(x_S),abs(x_T)))
      else:
        ans_cand.append(abs(x_S)+abs(x_T)+min(abs(x_S),abs(x_T)))
  print(int(min(ans_cand)))

Submission status: Time Limit Exceeded

Solution code:
import math

A,B,Q = map(int, input().split())
S=[0]*A
T=[0]*B
for i in range(A):
  S[i] = int(input())
for i in range(B):
  T[i] = int(input())
S.append(10**11)
S.insert(0,(-1)*(10**11))
T.append(10**11)
T.insert(0,(-1)*(10**11))
for i in range(Q):
  x = int(input())
  floor = 0
  ceil = len(S)-1
  while ceil-floor > 1:
    half = math.floor((floor+ceil)/2)
    s = S[half]
    if s < x:
      floor = half
    else:
      ceil = half
  nearest_x_S = [S[floor]-x, S[ceil]-x]
        
  floor = 0
  ceil = len(T)-1
  while ceil-floor > 1:
    half = math.floor((floor+ceil)/2)
    t = T[half]
    if t < x:
      floor = half
    else:
      ceil = half
  nearest_x_T = [T[floor]-x, T[ceil]-x]
  
  ans_cand = []
  for x_S in nearest_x_S:
    for x_T in nearest_x_T:
      if x_S*x_T > 0:
        ans_cand.append(max(abs(x_S),abs(x_T)))
      else:
        ans_cand.append(abs(x_S)+abs(x_T)+min(abs(x_S),abs(x_T)))
  print(int(min(ans_cand)))

Submission status: Time Limit Exceeded

Solution code:
import math

A,B,Q = map(int, input().split())
S=[0]*A
T=[0]*B
for i in range(A):
  S[i] = int(input())
for i in range(B):
  T[i] = int(input())
S.append(10**11)
S.insert(0,(-1)*(10**11))
T.append(10**11)
T.insert(0,(-1)*(10**11))
for i in range(Q):
  x = int(input())
  floor = 0
  ceil = len(S)-1
  while ceil-floor > 1:
    half = math.floor((floor+ceil)/2)
    s = S[half]
    if s < x:
      floor = half
    elif x < s:
      ceil = half
    else:
      floor = half
      ceil = half+1
  nearest_x_S = [S[floor]-x, S[ceil]-x]
        
  floor = 0
  ceil = len(T)-1
  while ceil-floor > 1:
    half = math.floor((floor+ceil)/2)
    t = T[half]
    if t < x:
      floor = half
    elif x < t:
      ceil = half
    else:
      floor = half
      ceil = half+1
  nearest_x_T = [T[floor]-x, T[ceil]-x]
  
  ans_cand = []
  for x_S in nearest_x_S:
    for x_T in nearest_x_T:
      if x_S*x_T > 0:
        ans_cand.append(max(abs(x_S),abs(x_T)))
      else:
        ans_cand.append(abs(x_S)+abs(x_T)+min(abs(x_S),abs(x_T)))
  print(int(min(ans_cand)))

Submission status: Time Limit Exceeded

Solution code:
import math

A,B,Q = map(int, input().split())
S=[0]*A
T=[0]*B
for i in range(A):
  S[i] = int(input())
for i in range(B):
  T[i] = int(input())
S.append(float('inf'))
S.insert(0,(-1)*float('inf'))
T.append(float('inf'))
T.insert(0,(-1)*float('inf'))
for i in range(Q):
  x = int(input())
  floor = 0
  ceil = len(S)-1
  index = math.floor(A/2)
  while True:
    s = S[index]
    s_before = S[index-1]
    s_next = S[index+1]
    if s < x:
      if x <= s_next:
        nearest_x_S = [s-x, s_next-x]
        break
      else:
        floor = index
        index = math.floor((floor+ceil)/2)
    elif x < s:
      if s_before <= x:
        nearest_x_S = [s_before-x, s-x]
        break
      else:
        ceil = index
        index = math.floor((floor+ceil)/2)
        
  floor = 0
  ceil = len(T)-1
  index = math.floor(B/2)
  while True:
    t = T[index]
    t_before = T[index-1]
    t_next = T[index+1]
    if t < x:
      if x <= t_next:
        nearest_x_T = [t-x, t_next-x]
        break
      else:
        floor = index
        index = math.floor((floor+ceil)/2)
    elif x < t:
      if t_before <= x:
        nearest_x_T = [t_before-x, t-x]
        break
      else:
        ceil = index
        index = math.floor((floor+ceil)/2)

  ans_cand = []
  for x_S in nearest_x_S:
    for x_T in nearest_x_T:
      if x_S*x_T > 0:
        ans_cand.append(max(abs(x_S),abs(x_T)))
      else:
        ans_cand.append(abs(x_S)+abs(x_T)+min(abs(x_S),abs(x_T)))
  print(int(min(ans_cand)))

Submission status: Time Limit Exceeded

Solution code:
import math

A,B,Q = map(int, input().split())
S=[0]*A
T=[0]*B
for i in range(A):
  S[i] = int(input())
for i in range(B):
  T[i] = int(input())
S.append(float('inf'))
S.insert(0,(-1)*float('inf'))
T.append(float('inf'))
T.insert(0,(-1)*float('inf'))
for i in range(Q):
  x = int(input())
  floor = 0
  ceil = len(S)-1
  index = math.floor(A/2)
  while True:
    if S[index] < x:
      if x <= S[index+1]:
        nearest_x_S = [S[index]-x, S[index+1]-x]
        break
      else:
        floor = index
        index = math.floor((floor+ceil)/2)
    elif x < S[index]:
      if S[index-1] <= x:
        nearest_x_S = [S[index-1]-x, S[index]-x]
        break
      else:
        ceil = index
        index = math.floor((floor+ceil)/2)
        
  floor = 0
  ceil = len(T)-1
  index = math.floor(B/2)
  while True:
    if T[index] < x:
      if x <= T[index+1]:
        nearest_x_T = [T[index]-x, T[index+1]-x]
        break
      else:
        floor = index
        index = math.floor((floor+ceil)/2)
    elif x < T[index]:
      if T[index-1] <= x:
        nearest_x_T = [T[index-1]-x, T[index]-x]
        break
      else:
        ceil = index
        index = math.floor((floor+ceil)/2)

  ans_cand = []
  for x_S in nearest_x_S:
    for x_T in nearest_x_T:
      if x_S*x_T > 0:
        ans_cand.append(max(abs(x_S),abs(x_T)))
      else:
        ans_cand.append(abs(x_S)+abs(x_T)+min(abs(x_S),abs(x_T)))
  print(int(min(ans_cand)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

A,B,Q = map(int, input().split())
S=np.zeros([A])
T=np.zeros([B])
X=np.zeros([Q])
for i in range(A):
  S[i] = int(input())
for i in range(B):
  T[i] = int(input())
S = np.concatenate([[float('inf')],S,[float('inf')]],axis=0)
T = np.concatenate([[float('inf')],T,[float('inf')]],axis=0)
for i in range(Q):
  x = int(input())
  dist_x_S = S - x
  dist_x_S_abs = np.abs(dist_x_S)
  min_index = np.argmin(dist_x_S_abs)
  if dist_x_S[min_index] > 0:
    nearest_x_S = [dist_x_S[min_index-1], dist_x_S[min_index]]
  elif dist_x_S[min_index] < 0:
    nearest_x_S = [dist_x_S[min_index], dist_x_S[min_index+1]]
  else:
    nearest_x_S = [0, dist_x_S[np.argmin([np.abs(dist_x_S[min_index-1]),np.argmin(dist_x_S[min_index+1])])]]
  
  dist_x_T = T - x
  dist_x_T_abs = np.abs(dist_x_T)
  min_index = np.argmin(dist_x_T_abs)
  if dist_x_T[min_index] > 0:
    nearest_x_T = [dist_x_T[min_index-1], dist_x_T[min_index]]
  elif dist_x_T[min_index] < 0:
    nearest_x_T = [dist_x_T[min_index], dist_x_T[min_index+1]]
  else:
    nearest_x_T = [0, dist_x_T[np.argmin([np.abs(dist_x_T[min_index-1]),np.argmin(dist_x_T[min_index+1])])]]  
  
  ans_cand = []
  for x_S in nearest_x_S:
    for x_T in nearest_x_T:
      if x_S*x_T > 0:
        ans_cand.append(max(abs(x_S),abs(x_T)))
      else:
        ans_cand.append(abs(x_S)+abs(x_T)+min(abs(x_S),abs(x_T)))
  print(int(min(ans_cand)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

A,B,Q = map(int, input().split())
S=np.zeros([A])
T=np.zeros([B])
X=np.zeros([Q])
for i in range(A):
  S[i] = int(input())
for i in range(B):
  T[i] = int(input())
for i in range(Q):
  x = int(input())
  dist_x_S = np.zeros([A,2])
  for j in range(A):
    dist_x_S[j][1] = S[j] - x
    dist_x_S[j][0] = np.abs(dist_x_S[j][1])
  sorted_dist_x_S = np.sort(dist_x_S,axis=0)
  if A > 1:
    nearest_x_S = np.array([sorted_dist_x_S[0][1],sorted_dist_x_S[1][1]])
  else:
    nearest_x_S = np.array([sorted_dist_x_S[0][1],float('inf')])
  
  dist_x_T = np.zeros([B,2])
  for j in range(B):
    dist_x_T[j][1] = T[j] - x
    dist_x_T[j][0] = np.abs(dist_x_T[j][1])
  sorted_dist_x_T = np.sort(dist_x_T,axis=0)
  if B > 1:
    nearest_x_T = np.array([sorted_dist_x_T[0][1],sorted_dist_x_T[1][1]])
  else:
    nearest_x_T = np.array([sorted_dist_x_T[0][1],float('inf')])
  
  ans_cand = []
  for x_S in nearest_x_S:
    for x_T in nearest_x_T:
      if x_S*x_T > 0:
        ans_cand.append(max(abs(x_S),abs(x_T)))
      else:
        ans_cand.append(abs(x_S)+abs(x_T)+min(abs(x_S),abs(x_T)))
  print(int(min(ans_cand)))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
A,B,Q=map(int,input().split())
S=[]
T=[]
X=[]
for i in range(A):
    S.append(int(input()))
for i in range(B):
    T.append(int(input()))
def rl(X,a):
    ind=bl(X,a)
    if ind>=len(X):
        return ind-1
    return ind
def ll(X,a):
    ind=bl(X,a)-1
    if ind<0:
        return ind+1
    return ind
def l(X,a):
    ind=bl(X,a)
    if ind>=len(X):
        ind1=ind-1
        return (ind1,ind1)
    elif ind-1<0:
        return (ind,ind)
    else:
        return (ind,ind-1)
t=[]
for i in range(A):
    ind1,ind2=l(T,S[i])
    mi=min(abs(T[ind1]-S[i]),abs(T[ind2]-S[i]))
    t.append(mi)
"""
    if abs(T[rl(T,S[i])]-S[i])>=abs(T[ll(T,S[i])]-S[i]):
        t.append(abs(T[ll(T,S[i])]-S[i]))
    else:
        t.append(abs(T[rl(T,S[i])])-S[i])
"""
s=[]
for i in range(B):
    ind1,ind2=l(S,T[i])
    mi=min(abs(S[ind1]-T[i]),abs(S[ind2]-T[i]))
    s.append(mi)
"""
    if abs(S[rl(S,T[i])]-T[i])>=abs(S[ll(S,T[i])]-T[i]):
        s.append(abs(S[ll(S,T[i])]-T[i]))
    else:
        s.append(abs(S[rl(S,T[i])])-T[i])
"""
for i in range(Q):
    x=int(input())
    a=rl(S,x)
    a=t[a]+abs(S[a]-x)

    b=ll(S,x)
    b=t[b]+abs(S[b]-x)

    c=rl(T,x)
    c=s[c]+abs(T[c]-x)

    d=ll(T,x)
    d=s[d]+abs(T[d]-x)

    print(min(a,b,c,d))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
a,b,q=map(int,input().split())
s=[]
t=[]
x=[]
s.append(-float("inf"))
t.append(-float("inf"))
for i in range(a):
    s.append(int(input()))
for i in range(b):
    t.append(int(input()))
s.append(float("inf"))
t.append(float("inf"))
for i in range(q):
    x=int(input())
    ans=float("inf")
    tmp_s_1=bisect_left(s,x)-1
    tmp_s_2=tmp_s_1+1
    tmp_s_1_t=bisect_left(t,s[tmp_s_1])
    tmp_s_2_t=bisect_left(t,s[tmp_s_2])
    ans=min(abs(x-s[tmp_s_1])+abs(s[tmp_s_1]-t[tmp_s_1_t-1]), abs(x-s[tmp_s_1])+abs(s[tmp_s_1]-t[tmp_s_1_t]), abs(x-s[tmp_s_2])+abs(s[tmp_s_2]-t[tmp_s_2_t-1]), abs(x-s[tmp_s_2])+abs(s[tmp_s_2]-t[tmp_s_2_t]))
    tmp_t_1=bisect_left(t,x)-1
    tmp_t_2=tmp_t_1+1
    tmp_t_1_s=bisect_left(s,t[tmp_t_1])
    tmp_t_2_s=bisect_left(s,t[tmp_t_2])
    ans=min(ans, abs(x-t[tmp_t_1])+abs(t[tmp_t_1]-s[tmp_t_1_s-1]), abs(x-t[tmp_t_1])+abs(t[tmp_t_1]-s[tmp_t_1_s]), abs(x-t[tmp_t_2])+abs(t[tmp_t_2]-s[tmp_t_2_s-1]), abs(x-t[tmp_t_2])+abs(t[tmp_t_2]-s[tmp_t_2_s]))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
a,b,q=map(int,input().split())
s=[]
t=[]
x=[]
s.append(-float("inf"))
t.append(-float("inf"))
for i in range(a):
    s.append(int(input()))
for i in range(b):
    t.append(int(input()))
s.append(float("inf"))
t.append(float("inf"))
s.sort()
t.sort()
for i in range(q):
    x=int(input())
    ans=float("inf")
    tmp_s_1=bisect_left(s,x)-1
    tmp_s_2=tmp_s_1+1
    tmp_s_1_t=bisect_left(t,s[tmp_s_1])
    tmp_s_2_t=bisect_left(t,s[tmp_s_2])
    ans=min(abs(x-s[tmp_s_1])+abs(s[tmp_s_1]-t[tmp_s_1_t-1]), abs(x-s[tmp_s_1])+abs(s[tmp_s_1]-t[tmp_s_1_t]), abs(x-s[tmp_s_2])+abs(s[tmp_s_2]-t[tmp_s_2_t-1]), abs(x-s[tmp_s_2])+abs(s[tmp_s_2]-t[tmp_s_2_t]))
    tmp_t_1=bisect_left(t,x)-1
    tmp_t_2=tmp_t_1+1
    tmp_t_1_s=bisect_left(s,t[tmp_t_1])
    tmp_t_2_s=bisect_left(s,t[tmp_t_2])
    ans=min(ans, abs(x-t[tmp_t_1])+abs(t[tmp_t_1]-s[tmp_t_1_s-1]), abs(x-t[tmp_t_1])+abs(t[tmp_t_1]-s[tmp_t_1_s]), abs(x-t[tmp_t_2])+abs(t[tmp_t_2]-s[tmp_t_2_s-1]), abs(x-t[tmp_t_2])+abs(t[tmp_t_2]-s[tmp_t_2_s]))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
from collections import deque
from fractions import gcd
#from math import factorial
from math import sqrt
from math import ceil
from itertools import permutations
from heapq import *
from collections import defaultdict
from copy import deepcopy

A,B,Q=map(int,input().split())
S=[]
T=[]
X=[]
for i in range(A):
    S.append(int(input()))
for i in range(B):
    T.append(int(input()))
def rl(X,a):
    ind=bl(X,a)
    if ind>=len(X):
        return ind-1
    return ind
def ll(X,a):
    ind=bl(X,a)-1
    if ind<0:
        return ind+1
    return ind
t=[]
for i in range(A):
    if abs(T[rl(T,S[i])]-S[i])>=abs(T[ll(T,S[i])]-S[i]):
        t.append(abs(T[ll(T,S[i])]-S[i]))
    else:
        t.append(abs(T[rl(T,S[i])])-S[i])
s=[]
for i in range(B):
    if abs(S[rl(S,T[i])]-T[i])>=abs(S[ll(S,T[i])]-T[i]):
        s.append(abs(S[ll(S,T[i])]-T[i]))
    else:
        s.append(abs(S[rl(S,T[i])])-T[i])

for i in range(Q):
    x=int(input())
    a=rl(S,x)
    a=t[a]+abs(S[a]-x)

    b=ll(S,x)
    b=t[b]+abs(S[b]-x)

    c=rl(T,x)
    c=s[c]+abs(T[c]-x)

    d=ll(T,x)
    d=s[d]+abs(T[d]-x)

    print(min(a,b,c,d))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
from collections import deque
from fractions import gcd
#from math import factorial
from math import sqrt
from math import ceil
from itertools import permutations
from heapq import *
from collections import defaultdict
from copy import deepcopy

A,B,Q=map(int,input().split())
S=[]
T=[]
X=[]
for i in range(A):
    S.append(int(input()))
for i in range(B):
    T.append(int(input()))
def rl(X,a):
    ind=bl(X,a)
    if ind>=len(X):
        return ind-1
    return ind
def ll(X,a):
    ind=bl(X,a)-1
    if ind<0:
        return ind+1
    return ind
for i in range(Q):
    x=int(input())
    a=S[rl(S,x)]
    ad=min(abs(T[rl(T,a)]-a),abs(T[ll(T,a)]-a))
    a=abs(a-x)+ad
    #print("a:",a)

    b=S[ll(S,x)]
    bd=min(abs(T[rl(T,b)]-b),abs(T[ll(T,b)]-b))
    b=abs(b-x)+bd
    #print("b:",b)

    c=T[rl(T,x)]
    cd=min(abs(S[rl(S,c)]-c),abs(S[ll(S,c)]-c))
    c=abs(c-x)+cd
    #print("c:",c)

    d=T[ll(T,x)]
    dd=min(abs(S[rl(S,d)]-d),abs(S[ll(S,d)]-d))
    d=abs(d-x)+dd
    #print("d:",d)

    print(min(a,b,c,d))

Submission status: Time Limit Exceeded

Solution code:
A, B, Q = map(int, input().split())
s, t, x = [], [], []
for i in range(A):
    s.append(int(input()))
for i in range(B):
    t.append(int(input()))
for i in range(Q):
    x.append(int(input()))


def find(target, loc):
    if len(target) > 2:
        if loc < target[len(target)//2]:
            return find(target[:len(target)//2+1], loc)
        else:
            return find(target[len(target)//2:], loc)
    elif len(target) == 2:
        if loc <= sum(target)/2:
            return target[0]
        else:
            return target[1]
    else:
        return target[0]


for x_i in x:
    # s -> t
    move_s = 0
    cur = find(s, x_i)
    move_s += abs(cur-x_i)
    end = find(t, cur)
    move_s += abs(end-cur)

    # t -> s
    move_t = 0
    cur = find(t, x_i)
    move_t += abs(cur-x_i)
    end = find(s, cur)
    move_t += abs(end-cur)

    print(min(move_s, move_t))

Submission status: Time Limit Exceeded

Solution code:
import bisect
a,b,q=map(int,input().split())
s=[]
t=[]
x=[]
s.append(-float("inf"))
t.append(-float("inf"))
for i in range(a):
    s.append(int(input()))
for i in range(b):
    t.append(int(input()))
s.append(float("inf"))
t.append(float("inf"))
s.sort()
t.sort()
for i in range(q):
    x=int(input())
    ans=float("inf")
    tmp_s_1=bisect.bisect_left(s,x)-1
    tmp_s_2=tmp_s_1+1
    tmp_s_1_t=bisect.bisect_left(t,s[tmp_s_1])
    tmp_s_2_t=bisect.bisect_left(t,s[tmp_s_2])
    ans=min(abs(x-s[tmp_s_1])+abs(s[tmp_s_1]-t[tmp_s_1_t-1]), abs(x-s[tmp_s_1])+abs(s[tmp_s_1]-t[tmp_s_1_t]), abs(x-s[tmp_s_2])+abs(s[tmp_s_2]-t[tmp_s_2_t-1]), abs(x-s[tmp_s_2])+abs(s[tmp_s_2]-t[tmp_s_2_t]))
    tmp_t_1=bisect.bisect_left(t,x)-1
    tmp_t_2=tmp_t_1+1
    tmp_t_1_s=bisect.bisect_left(s,t[tmp_t_1])
    tmp_t_2_s=bisect.bisect_left(s,t[tmp_t_2])
    ans=min(ans, abs(x-t[tmp_t_1])+abs(t[tmp_t_1]-s[tmp_t_1_s-1]), abs(x-t[tmp_t_1])+abs(t[tmp_t_1]-s[tmp_t_1_s]), abs(x-t[tmp_t_2])+abs(t[tmp_t_2]-s[tmp_t_2_s-1]), abs(x-t[tmp_t_2])+abs(t[tmp_t_2]-s[tmp_t_2_s]))
    print(ans)