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:
A, B, Q = map(int, input().split())
shrine = []
temple = []
for i in range(A):
    shrine.append(int(input()))
for i in range(B):
    temple.append(int(input()))

for i in range(Q):
    pos = int(input())
    nsh = [pos - shrine[i] for i in range(A)]
    ntem = [pos - temple[i] for i in range(B)]
    plusA, plusB, minusA, minusB = 2E10, 2E10, -2E10, -2E10
    for i in range(A):
        if(nsh[i]>= 0):
            plusA = min(plusA, nsh[i])
        else:
            minusA = max(minusA, nsh[i])
    for i in range(B):
        if(ntem[i]>= 0):
            plusB = min(plusB, ntem[i])
        else:
            minusB = max(minusB, ntem[i])
    lis = [max(plusA, plusB), abs(min(minusA, minusB)), abs(2*plusA-minusB), abs(2*minusA - plusB), abs(2*plusB - minusA), abs(2*minusB - plusA)]
    print(min(lis))

Submission status: Time Limit Exceeded

Solution code:
a, b, q = list(map(int, input().strip().split()))
s = []
t = []
for i in range(a):
    s.append(int(input()))

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

def binsearch_left_index(x, s, l, r):
    min_s = s[0]
    max_s = s[-1]
    if x < min_s:
        return None

    if x > max_s:
        return -1

    if r - l <= 1:
        return l

    if s[l] == x:
        return l;

    c = (l + r) // 2
    if s[c] > x:
        return binsearch_left_index(x, s, l, c)
    else:
        return binsearch_left_index(x, s, c, r)

def binsearch_right_index(x, s, l, r):
    min_s = s[0]
    max_s = s[-1]
    if x < min_s:
        return 0

    if x > max_s:
        return None

    return binsearch_left_index(x, s, l, r) + 1

def search(x):
    l_shrine = binsearch_left_index(x, s, 0, len(s))
    l_temple = binsearch_left_index(x, t, 0, len(t))
    r_shrine = binsearch_right_index(x, s, 0, len(s))
    r_temple = binsearch_right_index(x, t, 0, len(t))
# 左左と行く場合
    if l_shrine is None or l_temple is None:
        ll = 1e20
    else:
        ll = max(abs(s[l_shrine] - x), abs(t[l_temple] - x))

# 左神社右寺と行く場合
    if l_shrine is None or r_temple is None:
        lr1 = 1e20
    else:
        lr1 = abs(s[l_shrine] - x) + abs(t[r_temple] - s[l_shrine])

# 左寺右神社と行く場合
    if l_temple is None or r_shrine is None:
        lr2 = 1e20
    else:
        lr2 = abs(t[l_temple] - x) + abs(s[r_shrine] - l_temple)

# 右神社左寺と行く場合
    if r_shrine is None or l_temple is None:
        rl1 = 1e20
    else:
        rl1 = abs(s[r_shrine] - x) + abs(t[l_temple] - s[r_shrine])

# 右寺左神社と行く場合
    if l_shrine is None or r_temple is None:
        rl2 = 1e20
    else:
        rl2 = abs(t[r_temple] - x) + abs(s[l_shrine] - t[r_temple])

# 右右と行く場合
    if r_shrine is None or r_temple is None:
        rr = 1e20
    else:
        rr = max(abs(s[r_shrine] - x), abs(t[r_temple] - x))


    ans = min(ll, lr1, lr2, rl1, rl2, rr)
    return ans

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

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

[print(np.min([np.abs(b[np.argmin(np.abs(b-t))]-t) + np.min(np.abs(a-b[np.argmin(np.abs(b-t))])), np.abs(a[np.argmin(np.abs(a-t))]-t) + np.min(np.abs(b-a[np.argmin(np.abs(a-t))]))])) for t in s[-hint[2]:]]

Submission status: Time Limit Exceeded

Solution code:
a,b,q=(input().split())
a=int(a)
b=int(b)
q=int(q)
s = [int(input()) for i in range(a)]
s.sort()
t = [int(input()) for i in range(b)]
t.sort()
x = [int(input()) for i in range(q)]
#print(a,b,q,s,t,x)

for k in range(q):
    mins=float('inf')
    ptmins=0
    for i in range(a):
        if abs(s[i]-x[k]) < mins:
            ptmins=s[i]
            mins=abs(s[i]-x[k])
#print(ptmins,mins)

    ansa=float('inf')
    for i in range(b):
        if abs(t[i]-ptmins) < ansa:
            ansa=abs(t[i]-ptmins)
#print(mins+ansa)
    anssa=mins+ansa


    mint=float('inf')
    ptmint=0
    for i in range(b):
        if abs(t[i]-x[k]) < mint:
            ptmint=t[i]
            mint=abs(t[i]-x[k])
#print(ptmint,mint)
   
    ansb=float('inf')    
    for i in range(a):
        if abs(s[i]-ptmint) < ansb:
            ansb=abs(s[i]-ptmint)
#print(mint+ansb)
    anssb=mint+ansb
    
    print(min(anssa,anssb))

Submission status: Time Limit Exceeded

Solution code:
import sys

# スタート地点を与えると、最寄りの建物と、そこまでの移動距離を返す
# [(ind, dist)]
def search(start, lst):
    if start <= lst[0]:
        return [(0, lst[0] - start)]
    if lst[-1] <= start:
        return [(len(lst)-1, start - lst[-1])]

    # 間にある場合は二分探索
    return search_rec(start, lst, 0, len(lst) - 1)

def search_rec(start, lst, min_ind, max_ind):
    pivot_ind = (min_ind + max_ind) // 2
    if lst[pivot_ind] <= start and start <= lst[pivot_ind+1]:
        return [
            (pivot_ind, start - lst[pivot_ind]),
            (pivot_ind+1, lst[pivot_ind+1] - start),
        ]

    if start <= lst[pivot_ind]:
        return search_rec(start, lst, min_ind, pivot_ind)

    if lst[pivot_ind+1] <= start:
        return search_rec(start, lst, pivot_ind+1, max_ind)

    # ないと思う
    raise Exception('Not expected')


def solve(s_lst, t_lst, x):
    ans = []

    # 神社 → 寺ルート
    s_routes = search(x, s_lst)
    ##### print("{}, {}".format(x, s_routes)) ########
    for s_ind, s_dist in s_routes:
        tmp = [ s_dist + t_dist for t_ind, t_dist in search(s_lst[s_ind], t_lst)]
        #### print(tmp) ####
        ans.extend(tmp)

    # 寺 → 神社ルート
    t_routes = search(x, t_lst)
    ### print("{}, {}".format(x, t_routes)) ########
    for t_ind, t_dist in t_routes:
        tmp = [ t_dist + s_dist for s_ind, s_dist in search(t_lst[t_ind], s_lst)]
        ### print(tmp) ############
        ans.extend(tmp)

    # 小さいほうを選択
    return min(ans)

def main():
    line = sys.stdin.readline()
    line = line.rstrip()
    lst = line.split()

    a = int(lst[0])
    b = int(lst[1])
    q = int(lst[2])

    s_lst = []
    t_lst = []

    for i in range(a):
        line = sys.stdin.readline()
        s = int(line.rstrip())
        s_lst.append(s)

    for i in range(b):
        line = sys.stdin.readline()
        t = int(line.rstrip())
        t_lst.append(t)

    for i in range(q):
        line = sys.stdin.readline()
        x = int(line.rstrip())
        ans = solve(s_lst, t_lst, x)

        print(ans)

    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Time Limit Exceeded

Solution code:
def split_x(L, x):
    L_i = list(i if x > l else next(iter([])) for i, l in enumerate(L))
    if L_i == []:
        L_L = []
        L_R = L
    else:
        L_L = L[:L_i[-1]+1]
        L_R = L[ L_i[-1]+1:]
    return L_L, L_R

A, B, Q = 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)]


for x in X:
    res = []
    S_L, S_R = split_x(S, x)
    T_L, T_R = split_x(T, x)
    # R方向に神社・寺
    try:
        res.append(max(S_R[0], T_R[0]) - x)
    except:
        pass
    # L方向に神社・寺
    try:
        res.append(x - min(S_L[-1], T_L[-1]))
    except:
        pass
    # R方向に神社、L方向に寺
    try:
        res.append((S_R[0] - x) * 2 + (x - T_L[-1]))
    except:
        pass
    # L方向に神社、R方向に寺
    try:
        res.append((x - S_L[-1]) * 2 + (T_R[0] - x))
    except:
        pass
    # R方向に寺、L方向に神社
    try:
        res.append((T_R[0] - x) * 2 + (x - S_L[-1]))
    except:
        pass
    # L方向に寺、R方向に神社
    try:
        res.append((x - T_L[-1]) * 2 + (S_R[0] - x))
    except:
        pass
    print(min(res))

Submission status: Time Limit Exceeded

Solution code:
import bisect

f_inf = float('inf')


def cal(syurui, d, index):
    if d == 'e':
        return syurui[index]
    elif d == 'w':
        return syurui[index - 1]


A, B, Q = map(int, input().split())
s = [int(input()) for i in range(A)]
s.sort()
t = [int(input()) for i in range(B)]
t.sort()

for i in range(Q):
    x = int(input())
    s_index = bisect.bisect_left(s, x)
    t_index = bisect.bisect_left(t, x)
    if s_index == len(s) and t_index == len(t):
        print(max(abs(x-s[s_index-1]), abs(x-t[t_index-1])))
    elif s_index == len(s):
        ｓ.insert(0, -f_inf)
        t.insert(0, -f_inf)
        print(min(max(abs(x-s[s_index]), abs(x-t[t_index])),
                  2*abs(x-s[s_index])+abs(x-t[t_index+1]), abs(x-s[s_index])+2*abs(x-t[t_index+1])))
    elif t_index == len(t):
        ｓ.insert(0, -f_inf)
        t.insert(0, -f_inf)
        print(min(max(abs(x-s[s_index]), abs(x-t[t_index])), 2*abs(x-s[s_index+1])+abs(x-t[t_index]),
                  abs(x-s[s_index+1])+2*abs(x-t[t_index])))
    else:
        ｓ.insert(0, -f_inf)
        t.insert(0, -f_inf)
        print(min(max(abs(x-s[s_index]), abs(x-t[t_index])), max(
            abs(x-s[s_index+1]), abs(x-t[t_index+1])), 2*abs(x-s[s_index+1])+abs(x-t[t_index]), 2*abs(x-s[s_index])+abs(x-t[t_index+1]), abs(x-s[s_index+1])+2*abs(x-t[t_index]), abs(x-s[s_index])+2*abs(x-t[t_index+1])))

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np

def getNearestValue(list, num):
    last=0

    for i in list:
        if i < num:
            last = i
        else:
            if last==0: 
                return i

            if num - last > i - num:
                return i
            else:
                return last

    return last

    # idx = np.searchsorted(list, num, side="left")
    # if idx > 0 and (idx == len(list) or abs(num - list[idx-1]) < abs(num - list[idx])):
    #     return list[idx-1]
    # else:
    #     return list[idx]

    # idx = np.abs(np.asarray(list) - num).argmin()
    # return list[idx]

def main():
    A, B, Q = map(int, input().split())  #複数数値入力
    S = [0] * A
    T = [0] * B
    X = [0] * 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[i] = int(input())

    for i in range(Q):
        # 1:神社先
        basyo1 = getNearestValue(S, X[i])   
        dist1 = abs(basyo1 - X[i])
        dist1 += abs(getNearestValue(T, basyo1) -basyo1)

        # 2:寺先
        basyo2 = getNearestValue(T, X[i])
        dist2 = abs(basyo2 - X[i])
        dist2 += abs(getNearestValue(S, basyo2) -basyo2)

        print(min(dist1, dist2))


main()

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)]
sortedx = sorted(x)

sidx=0
tidx=0
arr=[]
for xi in sortedx:
  s_left_min = 1<<35
  s_right_min = 1<<35
  if sidx < 0:
    sidx=0
  for i in range(sidx,A):
    si = s[i]
    if si < xi:
      s_left_min = min(s_left_min, xi-si)
    else:
      sidx=i-1
      s_right_min = si-xi
      break
  t_left_min = 1<<35
  t_right_min = 1<<35
  if tidx < 0:
    tidx=0
  for i in range(tidx,B):
    ti = t[i]
    if ti < xi:
      t_left_min = min(t_left_min, xi-ti)
    else:
      t_right_min = ti-xi
      tidx = i-1
      break
  arr.append(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))

for xi in x:
  print(arr[sortedx.index(xi)])

Submission status: Time Limit Exceeded

Solution code:
A,B,Q = map(int,input().split())
As = [int(input()) for a in range(A)]
Bs = [int(input()) for b in range(B)]
Xs = [int(input()) for q in range(Q)]
X_A = [[0 for a in range(len(As))] for x in range(len(Xs))]
X_B = [[0 for a in range(len(Bs))] for x in range(len(Xs))]
A_B = [[0 for a in range(len(Bs))] for x in range(len(As))]
B_A = [[0 for a in range(len(As))] for x in range(len(Bs))]
ans = []
for x in range(len(Xs)):
    for a in range(len(As)):
        X_A[x][a] = abs(Xs[x]-As[a])
    for b in range(len(Bs)):
        X_B[x][b] = abs(Xs[x]-Bs[b]) 
for a in range(len(As)):
    for b in range(len(Bs)):
        A_B[a][b] = abs(As[a]-Bs[b])
for b in range(len(Bs)):
    for a in range(len(As)):
        B_A[b][a] = abs(Bs[b]-As[a])
for (a,b) in zip(X_A,X_B):
    ascore = 0
    bscore = 0
    akouho = min(a)
    bkouho = min(b)
    ascore+=akouho
    ascore+=min(A_B[a.index(akouho)])
    bscore+=bkouho
    bscore+=min(B_A[b.index(bkouho)])
    ans.append(min(ascore,bscore))
for an in ans:
    print(an)

Submission status: Time Limit Exceeded

Solution code:
A,B,Q=list(map(int,input().split()))
s=[0]*(A+2)
t=[0]*(B+2)
X=[0]*Q
s[0] = -float('inf')
s[A+1] = float('inf')
t[0] = -float('inf')
t[B+1] = float('inf')
for i in range(1,A+1):
    s[i] = int(input())
for i in range(1,B+1):
    t[i] = int(input())
for i in range(Q):
    X[i] = int(input())

import bisect
import numpy as np

def dec(x,s,t):
    s_ = s-x
    t_ = t-x
    as_ = abs(s_)
    at_ = abs(t_)
    if np.sign(s_)*np.sign(t_) == -1:
        return as_ + at_ + min(as_, at_)
    else:
        return max(as_,at_)


for x in X:
    s_i = bisect.bisect_left(s,x)
    t_i = bisect.bisect_left(t,x)
    s_l = s[s_i-1]
    s_r = s[s_i]
    t_l = t[t_i-1]
    t_r = t[t_i]
    ans = dec(x,s_l,t_l)
    ans_ = dec(x,s_l,t_r)
    if ans > ans_:
        ans = ans_
    ans_ = dec(x,s_r,t_l)
    if ans > ans_:
        ans = ans_
    ans_ = dec(x,s_r,t_r)
    if ans > ans_:
        ans = ans_
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
a, b ,q = map(int, input().split())
a_list = [int(input()) for i in range(a)]
b_list = [int(input()) for i in range(b)]
for n in range(q):
    q_pt = int(input())
    l = []
    for a_pt in a_list:
        for b_pt in b_list:
            l.append(min(abs(q_pt-a_pt)+abs(a_pt-b_pt),abs(q_pt-b_pt)+abs(b_pt-a_pt)))
    print(min(l))

Submission status: Time Limit Exceeded

Solution code:
a, b, q = list(map(int, input().strip().split()))
s = []
t = []
for i in range(a):
    s.append(int(input()))

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

def binsearch_left_index(x, s, l, r):
    min_s = s[0]
    max_s = s[-1]
    if x < min_s:
        return None

    if x > max_s:
        return -1

    if r - l <= 1:
        return l

    if s[l] == x:
        return l;

    c = (l + r) // 2
    if s[c] > x:
        return binsearch_left_index(x, s, l, c)
    else:
        return binsearch_left_index(x, s, c, r)

def binsearch_right_index(x, s, l, r):
    min_s = s[0]
    max_s = s[-1]
    if x < min_s:
        return 0

    if x > max_s:
        return None

    return binsearch_left_index(x, s, l, r) + 1

def search(x):
# 左左と行く場合
    l_shrine = binsearch_left_index(x, s, 0, len(s))
    l_temple = binsearch_left_index(x, t, 0, len(t))
    if l_shrine is None or l_temple is None:
        ll = 1e20
    else:
        ll = max(abs(s[l_shrine] - x), abs(t[l_temple] - x))

# 左神社右寺と行く場合
    l_shrine = binsearch_left_index(x, s, 0, len(s))
    r_temple = binsearch_right_index(x, t, 0, len(t))
    if l_shrine is None or r_temple is None:
        lr1 = 1e20
    else:
        lr1 = abs(s[l_shrine] - x) + abs(t[r_temple] - s[l_shrine])

# 左寺右神社と行く場合
    l_temple = binsearch_left_index(x, t, 0, len(t))
    r_shrine = binsearch_right_index(x, s, 0, len(s))
    if l_temple is None or r_shrine is None:
        lr2 = 1e20
    else:
        lr2 = abs(t[l_temple] - x) + abs(s[r_shrine] - l_temple)

# 右神社左寺と行く場合
    r_shrine = binsearch_right_index(x, s, 0, len(s))
    l_temple = binsearch_right_index(x, t, 0, len(t))
    if r_shrine is None or l_temple is None:
        rl1 = 1e20
    else:
        rl1 = abs(s[r_shrine] - x) + abs(t[l_temple] - s[r_shrine])

# 右寺左神社と行く場合
    r_temple = binsearch_right_index(x, t, 0, len(t))
    l_shrine = binsearch_left_index(x, s, 0, len(s))
    if l_shrine is None or r_temple is None:
        rl2 = 1e20
    else:
        rl2 = abs(t[r_temple] - x) + abs(s[l_shrine] - t[r_temple])

# 右右と行く場合
    r_shrine = binsearch_right_index(x, s, 0, len(s))
    r_temple = binsearch_right_index(x, t, 0, len(t))
    if r_shrine is None or r_temple is None:
        rr = 1e20
    else:
        rr = max(abs(s[r_shrine] - x), abs(t[r_temple] - x))


    ans = min(ll, lr1, lr2, rl1, rl2, rr)
    return ans

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

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())
  s1=s[:]
  s1.append(x)
  s1.sort()
  j=s1.index(x)
  if j==0:
    kouhoA=[s[j]]
  elif j==A:
    kouhoA=[s[j-1]]
  else:
    kouhoA=[s[j],s[j-1]]
  t1=t[:]
  t1.append(x)
  t1.sort()
  k=t1.index(x)
  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:
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]
  dsl = x-shrine_l
  dsr = shrine_r-x

  temple_b = bisect_left(T, x)
  temple_l = T[temple_b-1]
  temple_r = T[temple_b]
  dtl = x-temple_l
  dtr = temple_r-x

  print(min(
    dsl if shrine_l < temple_l else dtl,
    dsr if shrine_r > temple_r else dtr,
    dsl * 2 + dtr,
    dsl + dtr * 2,
    dsr * 2 + dtl,
    dsr + dtl * 2
  ))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def check(x, al, bl):
    rcost = np.inf
    for a in al:
        tmp_c = abs(a - x)
        for b in bl:
            t = abs(b - a)
            rcost = min(rcost, tmp_c + t, abs(b - x) + t)

    print(int(rcost))


n = [int(each) for each in input().split()]
a, b, q = n[0], n[1], n[2]

sl = np.zeros(a)
tl = np.zeros(b)
xl = np.zeros(q)

for i in range(a):
    sl[i] = int(input())
for i in range(b):
    tl[i] = int(input())
for i in range(q):
    xl[i] = int(input())

result = []
for x in xl:
    check(x, sl, tl)

Submission status: Time Limit Exceeded

Solution code:
from copy import copy
data = input().split()  
an = int(data[0])
bn = int(data[1])
qn = int(data[2])

a = []
for i in range(an):
    a.append(int(input()))
b = []
for i in range(bn):
    b.append(int(input()))
q = []
for i in range(qn):
    q.append(int(input()))

#print(a, b, q)

def near(lis, po):
    dif = list(map(lambda x: abs(x-po), lis))
    ind = dif.index(min(dif))
    return lis[ind]-po

def nearnext(lis, start, end, now):
    for point in lis:
        if(start <= point and point <= end):
            return 0
    return near(lis, now)

for i in q:
    start=int(i)
    neara=near(a, start)
    #print(a, start)
    #print(neara)
    if(neara < 0):
        #print(nearnext(b, start+neara, start, start+neara))
        neara=abs(neara)+abs(nearnext(b, start+neara, start, start+neara))
    else:
        #print(nearnext(b, start, start+neara, start+neara))
        neara+=abs(nearnext(b, start, start+neara, start+neara))
    #print(neara)

    nearb=near(b, start)
    if(nearb < 0):
        nearb=abs(nearb)+abs(nearnext(a, start+nearb, start, start+nearb))
    else:
        nearb+=abs(nearnext(a, start, start+nearb, start+nearb))

    #print(neara, nearb)
    if(neara < nearb):
        print(neara)
    else:
        print(nearb)

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 (jin-x[i])<= 0]
    if len(j_list) != 0:
        j_w = j_list[-1] + x[i]
        t_list = [ter-j_w for ter in t if ter-j_w<=0]
        if len(t_list) != 0:
            t_w = t_list[-1] + j_w
            ans = min(route(x[i], j_w,t_w), ans)
        t_list = [ter-j_w for ter in t if ter-j_w>0]
        if len(t_list) != 0:
            t_e = t_list[0] + j_w
            ans = min(route(x[i], j_w,t_e), ans)
    j_list = [jin-x[i] for jin in s if (jin-x[i]) > 0]
    if len(j_list) != 0:
        j_e = j_list[0] + x[i]
        t_list = [ter-j_e for ter in t if ter-j_e <= 0]
        if len(t_list) != 0:
            t_w = t_list[-1] + j_e
            ans = min(route(x[i], j_e,t_w), ans)
        t_list = [ter-j_e for ter in t if ter-j_e > 0]
        if len(t_list) != 0:
            t_e = t_list[0] + j_e
            ans = min(route(x[i], j_e,t_e), ans)

    t_list = [ter-x[i] for ter in t if ter-x[i]<=0]
    if len(t_list) != 0:
        t_w = t_list[-1] + x[i]
        j_list = [jin-t_w for jin in s if jin-t_w<=0]
        if len(j_list) != 0:
            j_w = j_list[-1] + t_w
            ans = min(route(x[i], t_w,j_w), ans)
        j_list = [jin-t_w for jin in s if jin-t_w>0]
        if len(j_list) != 0:
            j_e = j_list[0] + t_w
            ans = min(route(x[i], t_w,j_e), ans)
    t_list = [ter-x[i] for ter in t if ter-x[i]>0]
    if len(t_list) != 0:
        t_e = t_list[0] + x[i]
        j_list = [jin-t_e for jin in s if jin-t_e<=0]
        if len(j_list) != 0:
            j_w = j_list[-1] + t_e
            ans = min(route(x[i], t_e,j_w), ans)
        j_list = [jin-t_e for jin in s if jin-t_e>0]
        if len(j_list) != 0:
            j_e = j_list[0] + t_e
            ans = min(route(x[i], t_e,j_e), ans)
    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)]
q = [int(input()) for i in range(Q)]
i= 0
j = 0
near_i = []
near_j = []
for i in range(A):
    while True:
        if j == B-1:
            near_i.append(j)
            break
        elif s[i] > t[j]:
            j = j+1
        else:
            if j != 0:
                if abs(s[i]-t[j]) > abs(s[i]-t[j-1]):
                    near_i.append(j-1)
                else:
                    near_i.append(j)
            else:
                near_i.append(0)
            break
i = 0
j = 0
for j in range(B):
    while True:
        if i == A-1:
            near_j.append(i)
            break
        elif t[j] > s[i]:
            i = i+1
        else:
            if i != 0:
                if abs(s[i]-t[j]) > abs(s[i-1]-t[j]):
                    near_j.append(i-1)
                else:
                    near_j.append(i)
            else:
                near_j.append(0)
            break
for item in q:
    i = 0
    j = 0
    while s[i] < item and i<A-1:
        i = i+1
    while t[j] < item and j<B-1:
        j = j+1
    if i!= 0:
        s1 = i-1
    else:
        s1 = i
    if j!=0:
        t1 = j-1
    else:
        t1 = j
    s2 = i
    t2 = j
    list = [abs(s[s1]-item)+abs(t[near_i[s1]]-s[s1]),abs(s[s2]-item)+abs(t[near_i[s2]]-s[s2]),
    abs(t[t1]-item)+abs(s[near_j[t1]]-t[t1]),abs(t[t2]-item)+abs(s[near_j[t2]]-t[t2])]
    print(min(list))

Submission status: Time Limit Exceeded

Solution code:
import bisect

A, B, Q = map(int, input().split())
s = [None] * A
t = [None] * B
x = [None] * 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[i] = int(input())

s.sort()
t.sort()

def calc(s, t, x):
    len_s = len(s)
    len_t = len(t)

    def f_nishi_pos(l, x):
        p1 = bisect.bisect_left(l, x)
        p2 = bisect.bisect_right(l, x)
        if p2 == len(l):
            return p1-1
        if l[p1] == l[p2]:
            return max(p2-1, 0)
        else:
            return p1

    def f_higashi_pos(l, x):
        p1 = bisect.bisect_left(l, x)
        p2 = bisect.bisect_right(l, x)
        if p1 == len(l):
            return p1-1
        if l[p1] == l[p2]:
            return min(p1, len(l)-1)
        else:
            return p1

    # 神社 -> 寺
    ## 西の神社
    j_nishi_pos = f_nishi_pos(s, x)
    j_nishi = s[j_nishi_pos]
    ## 東の神社
    j_higashi_pos = f_higashi_pos(s, x)
    j_higashi = s[j_higashi_pos]

    ## 西の神社の西の寺
    j_nishi_t_nishi_pos = f_nishi_pos(t, j_nishi)
    j_nishi_t_nishi = t[j_nishi_t_nishi_pos]
    ## 西の神社の東の寺
    j_nishi_t_higashi_pos = f_higashi_pos(t, j_nishi)
    j_nishi_t_higashi = t[j_nishi_t_higashi_pos]
    ## 東の神社の西の寺
    j_higashi_t_nishi = t[f_nishi_pos(t, j_higashi)]
    ## 東の神社の東の寺
    j_higashi_t_higashi = t[f_higashi_pos(t, j_higashi)]


    # 寺 -> 神社
    t_nishi = t[f_nishi_pos(t, x)]
    t_higashi = t[f_higashi_pos(t, x)]
    
    ## 西の寺の西の神社
    t_nishi_j_nishi = s[f_nishi_pos(s, t_nishi)]
    ## 西の寺の東の神社
    t_nishi_j_higashi = s[f_higashi_pos(s, t_nishi)]
    ## 東の寺の東の神社
    t_higashi_j_nishi = s[f_nishi_pos(s, t_higashi)]
    ## 東の寺の東の神社
    t_higashi_j_higashi = s[f_higashi_pos(s, t_higashi)]


    l = [
        abs(x - j_nishi) + abs(j_nishi - j_nishi_t_nishi),
        abs(x - j_nishi) + abs(j_nishi - j_nishi_t_higashi),
        abs(x - j_higashi) + abs(j_higashi - j_higashi_t_nishi),
        abs(x - j_higashi) + abs(j_higashi - j_higashi_t_higashi),
        abs(x - t_nishi) + abs(t_nishi - t_nishi_j_nishi),
        abs(x - t_nishi) + abs(t_nishi - t_nishi_j_higashi),
        abs(x - t_higashi) + abs(t_higashi - t_higashi_j_nishi),
        abs(x - t_higashi) + abs(t_higashi - t_higashi_j_higashi)
    ]


    return min(l)

for xx in x:
    print(calc(s, t, xx))

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]
  dsl = x-shrine_l
  dsr = shrine_r-x

  temple_b = bisect_left(T, x)
  temple_l = T[temple_b-1]
  temple_r = T[temple_b]
  dtl = x-temple_l
  dtr = temple_r-x

  ans = float('inf')
  tmp = dsl if shrine_l < temple_l else dtl
  ans = ans if ans < tmp else tmp
  tmp = dsr if shrine_r > temple_r else dtr
  ans = ans if ans < tmp else tmp
  tmp = dsl * 2 + dtr
  ans = ans if ans < tmp else tmp
  tmp = dsl + dtr * 2
  ans = ans if ans < tmp else tmp
  tmp = dsr * 2 + dtl
  ans = ans if ans < tmp else tmp
  tmp = dsr + dtl * 2
  ans = ans if ans < tmp else tmp
  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)]

for x in X:
  n = []
  l_1 = [abs(x-s) for s in S]
  for s in S:
    if abs(x-s) == min(l_1):
      m_1 = [min(l_1)+abs(s-t) for t in T]
      n.append(min(m_1))
  l_2 = [abs(x-t) for t in T]
  for t in T:
    if abs(x-t) == min(l_2):
      m_2 = [min(l_2)+abs(t-s) for s in S]
      n.append(min(m_2))
  print(min(n))