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:
# coding: utf-8
# Your code here!

import numpy as np

def getNear(list, num):
    """
    概要: リストからある値に最も近い値を返却する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

a,b,q = map(int,input().split())
s = []
t = []

for i in range(a):
    s.append(int(input()))
for i in range(b):
    t.append(int(input()))

s.sort()
t.sort()

    
for i in range(q):
    x = int(input())
    
    s1 = -1
    s2 = -1
    t1 = -1
    t2 = -1
    
    
    s_n = getNear(s,x)
    t_n = getNear(t,x)
    
    if(s_n == 0 and x < s[0]):
        s1 = s[0]
        s2 = -1
    elif(s_n == a-1 and s[a-1] < x):
        s1 = s[a-1]
        s2 = -2
    elif(s[s_n] < x):
        s1 = s[s_n]
        s2 = s[s_n + 1]
    else:
        s1 = s[s_n - 1]
        s2 = s[s_n]

    if(t_n == 0 and x < t[0]):
        t1 = t[0]
        t2 = -1
    elif(t_n == b-1 and t[b-1] < x):
        t1 = t[b-1]
        t2 = -2
    elif(t[t_n] < x):
        t1 = t[t_n]
        t2 = t[t_n + 1]
    else:
        t1 = t[t_n - 1]
        t2 = t[t_n]
    
    
    if(s2 == t2 == -1):
        ans = max(s1,t1) - x
    elif(s2 == t2 == -2):
        ans = x - min(s1,t1)
    
    elif(s2 == -1 and t2 == -2):
        ans = min( abs(s1 -x) + abs(t1 - s1) , abs(t1 - x) + abs(t1-s1))

    elif(s2 == -2 and t2 == -1):
        ans = min( abs(s1 -x) + abs(t1 - s1) , abs(t1 - x) + abs(t1-s1))
        
    elif(s2 == -1):
        ans = min( x - t1 + abs(s1 - t1), t2 - x + abs(s1 - t2), abs(s1 - x) + min(abs(s1 - t1), abs(s1 - t2)))
         
    elif(s2 == -2):
        ans = min( x - t1 + abs(s1 - t1), t2 - x + abs(s1 - t2), abs(s1 - x) + min(abs(s1 - t1), abs(s1 - t2)))
    
    
    elif(t2 == -1):
        ans = min( x - s1 + abs(t1 - s1), s2 - x + abs(t1 - s2), abs(t1 - x) + min(abs(t1 - s1), abs(t1 - s2)))
        
    elif(t2 == -2):
        ans = min( x - s1 + abs(t1 - s1), s2 - x + abs(t1 - s2), abs(t1 - x) + min(abs(t1 - s1), abs(t1 - s2)))
        
    else:
        ans = min(x - min(s1,t1), max(s2,t2) - x)
    
    
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

hint = list(map(int, input().split()))
s = [int(input()) for i in range(sum(hint))]
#print(s)

a = np.asarray(s[:hint[0]])
b = np.asarray(s[hint[0]:-hint[2]])
sum = 0
for t in s[-hint[2]:]:
    a_dis = a[np.argmin(np.abs(a-t))]
    b_dis = b[np.argmin(np.abs(b-t))]
    a_d = np.abs(a_dis-t)
    b_d = np.abs(b_dis-t)
    print(np.min([b_d + np.min(np.abs(a-b_dis)), a_d + np.min(np.abs(b-a_dis))]))

Submission status: Time Limit Exceeded

Solution code:
def searchDL(s, x):
    if x <= s[0]:
        dist = s[0] - x
        loc = s[0]
        return dist, loc, dist, loc
    elif s[len(s) - 1] <= x:
        dist = x - s[len(s) - 1]
        loc = s[len(s) - 1]
        return dist, loc, dist, loc
    else:
        for i in range(0, len(s) - 1):
            if s[i] <= x and x <= s[i + 1]:
                if (x - s[i]) < (s[i + 1] - x):
                    dist = x - s[i]
                    loc = s[i]
                    return dist, loc, dist, loc
                elif (x - s[i]) > (s[i + 1] - x):
                    dist = s[i + 1] - x
                    loc = s[i + 1]
                    return dist, loc, dist, loc
                else:
                    dist1 = x - s[i]
                    loc1 = s[i]
                    dist2 = s[i + 1] - x
                    loc2 = s[i + 1]
                    return dist1, loc1, dist2, loc2

A, B, Q = list(map(int, input().split()))

s = []
for i in range(A):
    s.append(int(input()))

t = []
for i in range(B):
    t.append(int(input()))

for i in range(Q):
    x = int(input())
    d1_1a, l1_1a, d1_1b, l1_1b = searchDL(s, x)
    d1_2a, l1_2a, d1_2b, l1_2b = searchDL(t, l1_1a)
    d1_3a, l1_3a, d1_3b, l1_3b = searchDL(t, l1_1b)
    
    d2_1a, l2_1a, d2_1b, l2_1b = searchDL(t, x)
    d2_2a, l2_2a, d2_2b, l2_2b = searchDL(s, l2_1a)
    d2_3a, l2_3a, d2_3b, l2_3b = searchDL(s, l2_1b)
    
    print(min(d1_1a + d1_2a, d1_1a + d1_3a, d2_1a + d2_2a, d2_1a + d2_3a))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
A, B, Q = list(map(int, input().split()))
s = [int(input()) for i in range(A)]
t = [int(input()) for i in range(B)]
s.append(-100000000000);s.append(100000000000)
t.append(-100000000000);t.append(100000000000)
s = sorted(s, reverse=False)
t = sorted(t, reverse=False)
sn = np.array(s)
tn = np.array(t)

for i in range(Q):
    xi = int(input())
    sr = sn[sn.searchsorted(xi)]
    sl = sn[sn.searchsorted(xi) - 1]
    tr = tn.searchsorted(sn[sn.searchsorted(xi)])
    tl = tn.searchsorted(sn[sn.searchsorted(xi) - 1])

    stot = min(abs(xi - sr) + abs(sr - tn[tr]), abs(xi - sr) + abs(sr - tn[tr - 1]),
               abs(xi - sl) + abs(sl - tn[tl]), abs(xi - sl) + abs(sl - tn[tl - 1]))

    tr = tn[tn.searchsorted(xi)]
    tl = tn[tn.searchsorted(xi) - 1]
    sr = sn.searchsorted(tn[tn.searchsorted(xi)])
    sl = sn.searchsorted(tn[tn.searchsorted(xi) - 1])

    ttos = min(abs(xi - tr) + abs(tr - sn[sr]), abs(xi - tr) + abs(tr - sn[sr - 1]),
               abs(xi - tl) + abs(tl - sn[sl]), abs(xi - tl) + abs(tl - sn[sl - 1]))
    print(min(stot, ttos))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

S, T, Q = map(int, input().split(' '))

s = []
t = []

for i in range(S):
    s.append(int(input()))
for i in range(T):
    t.append(int(input()))

for i in range(Q):
    news = np.array(s)
    newt = np.array(t)
    x = int(input())
    news -= x
    newt -= x
    dis_l_s, dis_r_s, dis_l_t, dis_r_t = (10**11,10**11,10**11,10**11)
    negas = []
    negat = []
    while True:
        if news.size == 0:
            break
        if news[0] >= 0:
            break
        else:
            negas.append(news[0])
            news = np.delete(news, 0)
    while True:
        if newt.size == 0:
            break
        if newt[0] >= 0:
            break
        else:
            negat.append(newt[0])
            newt = np.delete(newt, 0)


    if len(negas) > 0:
        dis_l_s = - negas[-1]
    if news.size > 0: #xが右端でない
        dis_r_s = news[0]
    if len(negat) > 0:
        dis_l_t = - negat[-1]
    if newt.size > 0:
        dis_r_t = newt[0]
    r1 = max(dis_l_s, dis_l_t)
    r2 = max(dis_r_s, dis_r_t)
    r3 = dis_l_s * 2 + dis_r_t
    r4 = dis_l_t * 2 + dis_r_s
    r5 = dis_r_s * 2 + dis_l_t
    r6 = dis_r_t * 2 + dis_l_s

    r = [r1,r2,r3,r4,r5,r6]
    print(min(r))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
A, B, Q = map(int,input().split())
s_list = [int(input()) for i in range(A)]
t_list = [int(input()) for i in range(B)]
x_list = [int(input()) for i in range(Q)]


def get_dist_to_first_cp(x,li):
    dist1 = [l - x  for l in li]
    abs_dist1 = list(map(abs,dist1))
    dist_to_first_cp = min(abs_dist1)
    first_cp_num = np.argmin(abs_dist1)
    first_cp_pos = x + dist1[first_cp_num]
    return dist_to_first_cp, first_cp_pos
    


u_list = s_list + t_list
for i, x in enumerate(x_list):
    # shrine first
    dist_to_first_cp, first_cp_pos = get_dist_to_first_cp(x,s_list)
    dist2 = [t - first_cp_pos for t in t_list]
    dist_to_sec_cp = min(map(abs,dist2))
    ans_s = dist_to_first_cp + dist_to_sec_cp
    # temple first
    dist_to_first_cp, first_cp_pos = get_dist_to_first_cp(x,t_list)
    dist2 = [s - first_cp_pos for s in s_list]
    dist_to_sec_cp = min(map(abs,dist2))
    
    ans_t = dist_to_first_cp + dist_to_sec_cp

    print(min(ans_s,ans_t))

Submission status: Time Limit Exceeded

Solution code:
import bisect
a,b,q=map(int,input().split())
s=sorted([int(input()) for i in range(a)])
t=sorted([int(input()) for i in range(b)])
for i in range(q):
    ans=999999999999
    x=int(input())
    w=bisect.bisect_left(s,x)
    for j in range(2):
        if not 0<=w-j<len(s):
            continue
        z=bisect.bisect_left(t,s[w-j])
        for k in range(2):
            if not 0<=z-k<len(t):
                continue
            ans=min(ans,abs(x-s[w-j])+abs(s[w-j]-t[z-k]))
    w=bisect.bisect_left(t,x)
    for j in range(2):
        if not 0<=w-j<len(t):
            continue
        z=bisect.bisect_left(s,t[w-j])
        for k in range(2):
            if not 0<=z-k<len(s):
                continue
            ans=min(ans,abs(x-t[w-j])+abs(t[w-j]-s[z-k]))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

hint = list(map(int, input().split()))
s = [int(input()) for i in range(sum(hint))]
#print(s)

a = np.asarray(s[:hint[0]])
b = np.asarray(s[hint[0]:-hint[2]])
sum = 0
for t in s[-hint[2]:]:
    a_dis = a[np.argmin(np.abs(a-t))]
    b_dis = b[np.argmin(np.abs(b-t))]
    a_d = np.abs(a_dis-t)
    b_d = np.abs(b_dis-t)
    cand1 = b_d + np.min(np.abs(a-b_dis))
    cand2 = a_d + np.min(np.abs(b-a_dis))
    print(np.min([cand1, cand2]))

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 _min_idx(arr):
  abs_arr = list(map(abs, arr))
  idx = [i for i, x in enumerate(abs_arr) if x == min(abs_arr)]
  return(idx)

def min_idx(arr, x):
  ar = [d - x for d in arr]
  return(_min_idx(ar))

  
for q in range(len(x)):
  xx = x[q]
  ss = [d - xx for d in s]
  tt = [d - xx for d in t]
  
  cost_s = 0
  # pattern1 sから
  cost_s = min(map(abs, ss))
  idx = min_idx(s, xx)

  for i in idx:
    idx_next = min_idx(t, s[i])
    cost_s += abs(t[idx_next[0]] - s[i])

  cost_t = 0
  # pattern2 tから
  cost_t = min(map(abs, tt))
  idx = min_idx(t, xx)
  
  for i in idx:
    idx_next = min_idx(s, t[i])
    cost_t += abs(s[idx_next[0]] - t[i])

  if cost_s < cost_t:
    print(cost_s)
  else:
    print(cost_t)

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

def bs(z, st):
    l = 0
    r = len(st) - 1
    while r - l != 1:
        m = (l + r) // 2
        if st[m] == z:
            return m
        elif st[m] < z:
            l = m
        else:
            r = m
    return l

for xi in x:
    tmps = []
    tmpt = []
    if xi <= s[0]:
        tmps.append(s[0] - xi)
    elif s[-1] <= xi:
        tmps.append(s[-1] - xi)
    else:
        tmp = bs(xi, s)
        tmps.append(s[tmp] - xi)
        tmps.append(s[tmp + 1] - xi)

    if xi <= t[0]:
        tmpt.append(t[0] - xi)
    elif t[-1] <= xi:
        tmpt.append(t[-1] - xi)
    else:
        tmp = bs(xi, t)
        tmpt.append(t[tmp] - xi)
        tmpt.append(t[tmp + 1] - xi)
    anss = []
    for i in tmps:
        for j in tmpt:
            if i // abs(i) == j // abs(j):
                anss.append(max(abs(i), abs(j)))
            else:
                maxij = max(abs(i), abs(j)) 
                minij = min(abs(i), abs(j)) 
                anss.append(abs(maxij + minij * 2))
    anss.sort()
    print(anss[0])

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

for xi in x:
  s_left_min = 1<<35
  s_right_min = 1<<35
  for si in s:
    if si < xi:
      s_left_min = min(s_left_min, xi-si)
    else:
      s_right_min = si-xi
      break
  t_left_min = 1<<35
  t_right_min = 1<<35
  for ti in t:
    if ti < xi:
      t_left_min = min(t_left_min, xi-ti)
    else:
      t_right_min = ti-xi
      break
  print(min(max(s_left_min,t_left_min),max(s_right_min,t_right_min),s_left_min*2+t_right_min,t_left_min*2+s_right_min,s_right_min*2+t_left_min,t_right_min*2+s_left_min))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

hint = list(map(int, input().split()))
a = []
for i in range(hint[0]):
    a.append(int(input()))
b = []
for i in range(hint[1]):
    b.append(int(input()))
c = []
for i in range(hint[2]):
    c.append(int(input()))

a = np.asarray(a)
b = np.asarray(b)
sum = 0
for t in c:
    a_dis = a[np.argmin(np.abs(a-t))]
    b_dis = b[np.argmin(np.abs(b-t))]
    a_d = np.abs(a_dis-t)
    b_d = np.abs(b_dis-t)
    cand1 = b_d + np.min(np.abs(a-b_dis))
    cand2 = a_d + np.min(np.abs(b-a_dis))
    print(np.min([cand1, cand2]))

Submission status: Time Limit Exceeded

Solution code:
A,B,Q=map(int,input().split())
s=[]
t=[]
for i in range(A):
  s.append(int(input()))
for i in range(B):
  t.append(int(input()))
for i in range(Q):
  x=int(input())
  j=0
  while j<A:
    if x-s[j]>0:
      j+=1
    else:
      break
  if j==0:
    kouhoA=[s[j]]
  elif j==A:
    kouhoA=[s[j-1]]
  else:
    kouhoA=[s[j],s[j-1]]
  k=0
  while k<B:
    if x-t[k]>0:
      k+=1
    else:
      break
  if k==0:
    kouhoB=[t[k]]
  elif k==B:
    kouhoB=[t[k-1]]
  else:
    kouhoB=[t[k],t[k-1]]
  if len(kouhoA)==1:
    if len(kouhoB)==1:
      ans=min([abs(x-kouhoA[0])+abs(kouhoA[0]-kouhoB[0]),abs(x-kouhoB[0])+abs(kouhoB[0]-kouhoA[0])])
    else:
      ans=min([abs(x-kouhoA[0])+abs(kouhoA[0]-kouhoB[0]),abs(x-kouhoB[0])+abs(kouhoB[0]-kouhoA[0]),abs(x-kouhoA[0])+abs(kouhoA[0]-kouhoB[1]),abs(x-kouhoB[1])+abs(kouhoB[1]-kouhoA[0])])
  else:
    if len(kouhoB)==1:
      ans=min([abs(x-kouhoA[0])+abs(kouhoA[0]-kouhoB[0]),abs(x-kouhoB[0])+abs(kouhoB[0]-kouhoA[0]),abs(x-kouhoA[1])+abs(kouhoA[1]-kouhoB[0]),abs(x-kouhoB[0])+abs(kouhoB[0]-kouhoA[1])])
    else:
      ans=min([abs(x-kouhoA[0])+abs(kouhoA[0]-kouhoB[0]),abs(x-kouhoB[0])+abs(kouhoB[0]-kouhoA[0]),abs(x-kouhoA[1])+abs(kouhoA[1]-kouhoB[1]),abs(x-kouhoB[1])+abs(kouhoB[1]-kouhoA[1]),abs(x-kouhoA[1])+abs(kouhoA[1]-kouhoB[0]),abs(x-kouhoB[0])+abs(kouhoB[0]-kouhoA[1]),abs(x-kouhoA[0])+abs(kouhoA[0]-kouhoB[1]),abs(x-kouhoB[1])+abs(kouhoB[1]-kouhoA[0])])
  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.sort()
t.sort()

def bs(z, st):
    l = 0
    r = len(st) - 1
    while r - l != 1:
        m = (l + r) // 2
        if st[m] == z:
            return m
        elif st[m] < z:
            l = m
        else:
            r = m
    return l

for xi in x:
    tmps = []
    tmpt = []
    if xi <= s[0]:
        tmps.append(s[0] - xi)
    elif s[-1] <= xi:
        tmps.append(s[-1] - xi)
    else:
        tmp = bs(xi, s)
        tmps.append(s[tmp] - xi)
        tmps.append(s[tmp + 1] - xi)

    if xi <= t[0]:
        tmpt.append(t[0] - xi)
    elif t[-1] <= xi:
        tmpt.append(t[-1] - xi)
    else:
        tmp = bs(xi, t)
        tmpt.append(t[tmp] - xi)
        tmpt.append(t[tmp + 1] - xi)
    anss = []
    for i in tmps:
        for j in tmpt:
            if i // abs(i) == j // abs(j):
                anss.append(max(abs(i), abs(j)))
            else:
                maxij = max(abs(i), abs(j)) 
                minij = min(abs(i), abs(j)) 
                anss.append(abs(maxij + minij * 2))
    anss.sort()
    print(anss[0])

Submission status: Time Limit Exceeded

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

result = [100000]*Q
c = 0
for c, k in enumerate(x):
    shrine_f = 0
    temple_f = 0
    cand = list()
    # shrine first, get the min distance shrines
    s0 = [abs(s[i]-k) for i in range(A)]
    # print('s0', s0)
    min_s = min(s0)
    cand_s = [i for i, e in enumerate(s0) if e == min_s]
    # print(cand_s)
    for i in cand_s:
        t1 = [abs(t[j]-s[i]) for j in range(B)]
        cand.append(min_s + min(t1))

    # temple first
    t0 = [abs(t[i] - k) for i in range(B)]
    # print('t0', t0)
    min_t = min(t0)
    cand_t = [i for i, e in enumerate(t0) if e == min_t]
    # print(cand_t)
    for i in cand_t:
        s1 = [abs(s[j] - t[i]) for j in range(A)]
        # print('s1', s1)
        cand.append(min_t + min(s1))

    # print('cand', cand)
    result[c] = min(cand)

for i in result:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
a,b,q = map(int, input().split(" "))
A,B,Q = [],[],[]
for i in range(a+b+q):
  if i<a:
    A.append(int(input()))
  elif i<a+b:
    B.append(int(input()))
  else:
    Q.append(int(input()))  
    
for j in Q:
  mina,minb=0,0
  pos=0
  posa,posb=0,0
  needa=9999999999999999999999999999999999999
  for k in A:
    if needa>abs(k-j):
      needa=abs(k-j)
      posa=k
  needb=999999999999999999999999999999999999999
  for l in B:
    if needb>abs(l-j):
      needb=abs(l-j)
      posb=l    
  needa2=99999999999999999999999999999999999999
  minb+=needb
  pos=posb
  for m in A:
    if needa2>abs(pos-m):
      needa2=abs(pos-m)   
  minb+=needa2 
  needb2=99999999999999999999999999999999999
  mina+=needa
  pos=posa
  for n in B:
    if needb2>abs(pos-n):
      needb2=abs(pos-n) 
  mina+=needb2
  print(min(mina,minb))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
A, B, Q = map(int, input().split())
BIG = 10**10 + 1
S = [-BIG] + sorted([int(input()) for _ in range(A)]) + [BIG*2]
T = [-BIG] + sorted([int(input()) for _ in range(B)]) + [BIG*2]
for _ in range(Q):
  x = int(input())
  shrine_b = bisect_left(S, x)
  shrine_l = S[shrine_b-1]
  shrine_r = S[shrine_b]
  temple_b = bisect_left(T, x)
  temple_l = T[temple_b-1]
  temple_r = T[temple_b]
  print(min(
    x-shrine_l if shrine_l < temple_l else x-temple_l,
    shrine_r-x if shrine_r > temple_r else temple_r-x,
    (x-shrine_l) * 2 + temple_r-x,
    x-shrine_l + (temple_r-x) * 2,
    (shrine_r-x) * 2 + x-temple_l,
    shrine_r-x + (x-temple_l) * 2
  ))

Submission status: Time Limit Exceeded

Solution code:
a, b, q = map(lambda x: int(x), input().split())

s = []
for i in range(a):
    s.append(int(input()))

t = []
for i in range(b):
    t.append(int(input()))

for i in range(q):
    x = int(input())

    distance = 2 * 10 ** 10
    #s east
    se = list(filter(lambda y: y-x >= 0, s))
    if len(se) > 0:
        sj = se[0]
        tmp = map(lambda y: abs(y - sj), t)
        tmp_distance = se[0] - x + min(tmp)
        if tmp_distance < distance:
            distance = tmp_distance
    #s west
    sw = list(reversed(list(filter(lambda y: y-x <= 0, s))))
    if len(sw) > 0:
        sj = sw[0]
        tmp = map(lambda y: abs(y - sj), t)
        tmp_distance = x - sw[0] + min(tmp)
        if tmp_distance < distance:
            distance = tmp_distance
    #t east
    te = list(filter(lambda y: y-x >= 0, t))
    if len(te) > 0:
        tj = te[0]
        tmp = map(lambda y: abs(y - tj), s)
        tmp_distance = te[0] - x + min(tmp)
        if tmp_distance < distance:
            distance = tmp_distance
    #t west
    tw = list(reversed(list(filter(lambda y: y-x <= 0, t))))
    if len(tw) > 0:
        tj = tw[0]
        tmp = map(lambda y: abs(y - tj), s)
        tmp_distance = x - tw[0] + min(tmp)

        if tmp_distance < distance:
            distance = tmp_distance

    print(distance)

Submission status: Time Limit Exceeded

Solution code:
# D
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 route(start, mid, end):
    return abs(start-mid) + abs(mid-end)

for i in range(q):
    ans = 10000000000000000000000000
    # jinja
    j_list = [jin-x[i] for jin in s]
    if len([y for y in j_list if y<=0]) != 0:
        j_w = max([y for y in j_list if y<=0]) + x[i]
        t_list = [ter-j_w for ter in t]
        if len([y for y in t_list if y<=0]) != 0:
            t_w = max([y for y in t_list if y<=0]) + j_w
            ans = min(route(x[i], j_w,t_w), ans)
        else:
            t_e = min([y for y in t_list if y>0]) + j_w
            ans = min(route(x[i], j_w,t_e), ans)
    if len([y for y in j_list if y>0]) != 0:
        j_e = min([y for y in j_list if y>0]) + x[i]
        t_list = [ter-j_e for ter in t]
        if len([y for y in t_list if y<=0]) != 0:
            t_w = max([y for y in t_list if y<=0]) + j_e
            ans = min(route(x[i], j_e,t_w), ans)
        else:
            t_e = min([y for y in t_list if y>0]) + j_e
            ans = min(route(x[i], j_e,t_e), ans)
    t_list = [ter-x[i] for ter in t]
    if len([y for y in t_list if y<=0]) != 0:
        t_w = max([y for y in t_list if y<=0]) + x[i]
        j_list = [jin-t_w for jin in s]
        if len([y for y in j_list if y<=0]) != 0:
            j_w = max([y for y in j_list if y<=0]) + t_w
            ans = min(route(x[i], t_w,j_w), ans)
        else:
            j_e = min([y for y in j_list if y>0]) + t_w
            ans = min(route(x[i], t_w,j_e), ans)
    if len([y for y in t_list if y>0]) != 0:
        t_e = min([y for y in t_list if y>0]) + x[i]
        j_list = [jin-t_e for jin in s]
        if len([y for y in j_list if y<=0]) != 0:
            j_w = max([y for y in j_list if y<=0]) + t_e
            ans = min(route(x[i], t_e,j_w), ans)
        else:
            j_e = min([y for y in j_list if y>0]) + t_e
            ans = min(route(x[i], t_e,j_e), ans)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def search(arry, target):
    left = 0
    right = len(arry) - 1

    while left <= right:
        mid = (left + right) // 2
        if mid == len(arry) - 1:
            return mid
        if arry[mid] <= target < arry[mid+1]:
            result = mid
            break
        elif arry[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
    if target - arry[mid] < arry[mid+1] - target:
        return mid
    else:
        return mid + 1


def near(a, t):
    return a[search(a, t)]


def walk(x):
    # print("target:", x)
    near_a = near(a_s, x)
    near_a_b = near(b_s, near_a)
    sum_ab = abs(near_a - x) + abs(near_a_b - near_a)
    # print("a", near_a, "ab", near_a_b, sum_ab)
    near_b = near(b_s, x)
    near_b_a = near(a_s, near_b)
    sum_ba = abs(near_b - x) + abs(near_b_a - near_b)
    # print("b", near_b, "ba", near_b_a, sum_ba)
    return sum_ab if sum_ab < sum_ba else sum_ba


A, B, Q = map(int, input().split())
a_s = []
b_s = []
# q_s = []
for _ in range(A):
    a_s.append(int(input()))
for _ in range(B):
    b_s.append(int(input()))
# print("===")
for _ in range(Q):
    q = int(input())
    print(walk(q))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def get_nearest(point, lst):
    """
    概要: リストからある値に最も近い値を返却する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(lst) - point).argmin()
    return lst[idx]

#def get_nearest(point, lst):
#    shortest = 1000000000000000
#    nearest = float("inf")
#    for x in lst:
#        dist = abs(x - point)
#        if dist < shortest:
#            shortest = dist
#            nearest = x
#    return nearest

#def exist_between(a, b, lst):
#    for x in lst:
#        if a <= x and x <= b:
#            return True
#    else:
#        return False

A, B, Q = [int(x) for x in input().split(" ")]
a = []
b = []
for i in range(A):
    a.append(int(input()))
for i in range(B):
    b.append(int(input()))
for i in range(Q):
    q = int(input())
    nearest_a = get_nearest(q, a)
    nearest_b = get_nearest(q, b)
#   print(q, nearest_a, nearest_b)
    
    if abs(nearest_a - q) < abs(nearest_b - q):
        nearer, farer = nearest_a, nearest_b
        nearer_list, farer_list = a, b
    else:
        nearer, farer = nearest_b, nearest_a
        nearer_list, farer_list = b, a

    nearer_first  = abs(q - nearer)
    nearer_first += abs(nearer - get_nearest(nearer, farer_list))

    farer_first  = abs(q - farer)
    farer_first += abs(farer - get_nearest(farer, nearer_list))

    answer = min(nearer_first, farer_first)

    print(answer)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

a,b,q = map(int,input().split())
s = []
t = []

for i in range(a):
    s.append(int(input()))
for i in range(b):
    t.append(int(input()))

s.sort()
t.sort()

    
for i in range(q):
    x = int(input())
    
    s1 = -1
    s2 = -1
    t1 = -1
    t2 = -1
    
    for j in range(a):
        if(j == 0 and s[0] > x):
            s1 = s[0]
            break
        
        elif(s[j] > x and x > s[j-1]):
            s1 = s[j-1]
            s2 = s[j]
            break

    if(s1 == -1):
        s1 = s[a-1]
        s2 = -2
    
    for j in range(b):
        if(j == 0 and t[0] > x):
            t1 = t[0]
            break
        
        elif(t[j] > x and x > t[j-1]):
            t1 = t[j-1]
            t2 = t[j]
            break
        
    if(t1 == -1):
        t1 = t[b-1]
        t2 = -2
    
    
    
    if(s2 == t2 == -1):
        ans = max(s1,t1) - x
    elif(s2 == t2 == -2):
        ans = x - min(s1,t1)
    
    elif(s2 == -1 and t2 == -2):
        ans = min( abs(s1 -x) + abs(t1 - s1) , abs(t1 - x) + abs(t1-s1))

    elif(s2 == -2 and t2 == -1):
        ans = min( abs(s1 -x) + abs(t1 - s1) , abs(t1 - x) + abs(t1-s1))
        
    elif(s2 == -1):
        ans = min( x - t1 + abs(s1 - t1), t2 - x + abs(s1 - t2), abs(s1 - x) + min(abs(s1 - t1), abs(s1 - t2)))
         
    elif(s2 == -2):
        ans = min( x - t1 + abs(s1 - t1), t2 - x + abs(s1 - t2), abs(s1 - x) + min(abs(s1 - t1), abs(s1 - t2)))
    
    
    elif(t2 == -1):
        ans = min( x - s1 + abs(t1 - s1), s2 - x + abs(t1 - s2), abs(t1 - x) + min(abs(t1 - s1), abs(t1 - s2)))
        
    elif(t2 == -2):
        ans = min( x - s1 + abs(t1 - s1), s2 - x + abs(t1 - s2), abs(t1 - x) + min(abs(t1 - s1), abs(t1 - s2)))
        
    else:
        ans = min(x - min(s1,t1), max(s2,t2) - x)
    
    
    print(ans)
        
    
    """
    
    ans = 9999999999
    if(s_x == t_x == 0):
        ans = min(s[0] - x, t[0] - x)
        
    elif(s_x == t_x == -1):
        ans = min(x - s[a-1], x - t[b-1])
        
    elif(s_x == 0 and t_x != -1):
        ans  = s[0] - x + min(abs(s[0] - t[t_x]),abs(s[0] - t[t_x - 1]))
        
    elif(s_x != -1 and t_x == 0):
        ans  = t[0] - x + min(abs(t[0] - s[s_x]),abs(t[0] - s[s_x - 1]))
    elif(s_x == -1 and t_x != 0):
        ans  = x - s[a-1] + min(abs(s[a-1] - t[t_x]),abs(s[a-1] - t[t_x - 1]))
    elif(s_x != 0 and t_x == -1):
        ans  = x - t[b-1] + min(abs(t[b-1] - s[s_x]),abs(t[b-1] - s[s_x - 1]))
    else:
    """

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def lower_bound(al, key):
    """
    一般に左側が満たしておらず、右側は満たしている判定基準(境目は一つ)ならlower_boundになる
    (条件を満たすもののうち、最小のインデックスを返す)
    単調にさえなっていれば、左右が逆になっていても検索には使える(ng/okも一緒に逆にする必要がある)
    """
    def isOk(a):
        # alの中でkey以上のアイテムのうち最小のインデックスを返す
        # upper_boundにする時にはa>key
        return a>=key

    ng = -1
    ok = len(al)

    while abs(ok-ng)>1:
        mid = (ok+ng)//2

        if isOk(al[mid]):
            ok = mid
        else:
            ng = mid

    return ok


a,b,q = map(int, input().split())
sl = [int(input()) for _ in range(a)]
tl = [int(input()) for _ in range(b)]
xl = [int(input()) for _ in range(q)]
# print(sl)
# print(tl)
for x in xl:
    si = lower_bound(sl,x)
    ti = lower_bound(tl,x)
    # print(x,si,ti)

    ssl = []
    if si==a:
        ssl.append(sl[-1])
    elif si==-1:
        ssl.append(sl[0])
    else:
        ssl.append(sl[si])
        if si>0:
            ssl.append(sl[si-1])
    ttl = []
    if ti==b:
        ttl.append(tl[-1])
    elif ti==-1:
        ttl.append(tl[0])
    else:
        ttl.append(tl[ti])
        if ti>0:
            ttl.append(tl[ti-1])

    res = -1
    for s in ssl:
        for t in ttl:
            if s>=x and t>=x:
                tmp = max(s-x, t-x)
            elif s<x and t<x:
                tmp = max(x-s, x-t)
            elif s>=x>=t:
                tmp = min(
                    2*(s-x)+(x-t),
                    (s-x)+2*(x-t)
                )
            else:
                tmp = min(
                    2*(x-s)+(t-x),
                    (x-s)+2*(t-x)
                )
            if res<0:
                res = tmp
            else:
                res = min(res,tmp)
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np


def find_nearest(array, value):
    idx = np.searchsorted(array, value, side="left")
    if idx > 0 and (idx == len(array) or math.fabs(value - array[idx - 1]) < math.fabs(value - array[idx])):
        return array[idx - 1]
    else:
        return array[idx]


A, B, Q = map(int, input().split())
s = np.array([int(input()) for _ in range(A)])
t = np.array([int(input()) for _ in range(B)])
x = np.array([int(input()) for _ in range(Q)])
for query in x:
    shrine = find_nearest(s, query)
    temple = find_nearest(t, query)
    planA = abs(query - shrine) + abs(find_nearest(t, shrine) - shrine)
    planB = abs(query - temple) + abs(find_nearest(s, temple) - temple)
    print(min(planA, planB))