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: Wrong Answer

Solution code:
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)
    farer = nearest_b if abs(nearest_a - q) < abs(nearest_b - q) else nearest_a
    nearer = nearest_a if abs(nearest_a - q) < abs(nearest_b - q) else nearest_b
    not_farer_list = a if abs(nearest_a - q) < abs(nearest_b - q) else b
    if exist_between(q, farer, not_farer_list):
        print(abs(farer - q))
    else:
        print(abs(nearer - q) + abs(farer - nearer))

Submission status: Wrong Answer

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

def main(s,t,xi):
    sidx=bisect.bisect_left(s,xi)
    if sidx==0:
        shidari=10**10
        smigi=s[sidx]-xi
    elif sidx==len(s):
        shidari=xi-s[sidx-1]
        smigi=10**10
    elif s[sidx]==xi:
        shidari=0
        smigi=0
    else:
        shidari=xi-s[sidx-1]
        smigi=s[sidx]-xi
    tidx=bisect.bisect_left(t,xi)
    if tidx==0:
        thidari=10**10
        tmigi=t[tidx]-xi
    elif tidx==len(t):
        thidari=xi-t[tidx-1]
        tmigi=10**10
    elif t[tidx]==xi:
        thidari=0
        tmigi=0
    else:
        thidari=xi-t[tidx-1]
        tmigi=t[tidx]-xi
    k=min(2*shidari+tmigi,2*tmigi+shidari,2*smigi+thidari,2*thidari+smigi)
    return min(max(thidari,shidari),max(tmigi,smigi),k)
for k in range(q):
    print(main(s,t,int(input())))

Submission status: Wrong Answer

Solution code:
import numpy as np
A,B,Q = map(int, input().split())

s_list = [int(input()) for _ in range(A)]
t_list = [int(input()) for _ in range(B)]
x_list = [int(input()) for _ in range(Q)]

print("s : ",s_list)
print("t : ",t_list)
print("x : ",x_list)

s_nearest_t = []
t_nearest_s = []

for s in s_list:
    t_dis = [abs(s-t) for t in t_list]
    s_nearest_t.append(np.min(t_dis))
for t in t_list:
    s_dis = [abs(s-t) for s in s_list]
    t_nearest_s.append(np.min(s_dis))


def get_ans(s_list, t_list, x):
    s_res = [abs(s-x) for s in s_list]
    t_res = [abs(t-x) for t in t_list]
    s_nearest = np.min(s_res)
    t_nearest = np.min(t_res)
    
    s_nearest_idx = s_res.index(s_nearest)
    t_nearest_idx = t_res.index(t_nearest)
    
    if s_nearest_t[s_nearest_idx] + s_nearest < t_nearest_s[t_nearest_idx] + t_nearest:
        ans = s_nearest_t[s_nearest_idx] + s_nearest
    else:
        ans = t_nearest_s[t_nearest_idx] + t_nearest
    
#     nearest = min(np.min(s_res), np.min(t_res))
    
#     ans = nearest
    
#     if np.min(s_res) < np.min(t_res):
#         x = s_list[np.argmin(s_res)]
#         t_res_ = [abs(t-x) for t in t_list]
#         ans += np.min(t_res_)
#     else:
#         x = t_list[np.argmin(t_res)]
#         s_res_ = [abs(s-x) for s in s_list]
#         ans += np.min(s_res_)
    return ans
        
for x in x_list:
    print(get_ans(s_list, t_list, x))

Submission status: Wrong Answer

Solution code:
import numpy as np


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 = [int(input()) for _ in range(Q)]

for x in X:
    R = []
    try:
        SSX0x = S[S > x][0] - x
    except:
        pass
    try:
        TTx0x = T[T > x][0] - x
    except:
        pass
    try:
        xSSx1 = x - S[S < x][-1]
    except:
        pass
    try:
        xTTx1 = x - T[T < x][-1]
    except:
        pass
    # +方向に神社・寺
    try:
        R.append(max(SSX0x, TTx0x))
    except:
        pass
    # -方向に神社・寺
    try:
        R.append(max(xSSx1, xTTx1))
    except:
        pass
    # +方向に神社、-方向に寺
    try:
        R.append(SSX0x * 2 + xTTx1)
    except:
        pass
    # -方向に神社、+方向に寺
    try:
        R.append(xSSx1 * 2 + TTx0x)
    except:
        pass
    # +方向に寺、-方向に神社
    try:
        R.append(TTx0x * 2 + xSSx1)
    except:
        pass
    # -方向に寺、+方向に神社
    try:
        R.append(xTTx1 * 2 + SSX0x)
    except:
        pass
    print(min(R))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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 _ in range(q):
  x = int(input())
  
  ans = [0,0,0]
  
  if x in s:
    sl = 0
    sr = 0
  else:
    i = bisect.bisect_left(s,x)
    if i == 0:
      sl = 100000000000
    else:
      sl = abs(s[i-1]-x)
    if i == a:
      sr = 100000000000
    else:
      sr = abs(s[i]-x)
  if x in t:
    tl = 0
    tr = 0
  else:
    i = bisect.bisect_left(t,x)
    if i == 0:
      tl = 100000000000
    else:
      tl = abs(t[i-1]-x)
    if i == b:
      tr = 100000000000
    else:
      tr = abs(t[i]-x)
  ans[0] = max(tl,sl)
  ans[1] = max(tr,sr)
  ans[2] = min(2*tl+sr,2*sl+tr,2*sr+tl,2*tr+sl)
  print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
def near(x, Y):
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x
    elif i == len(Y):
        return x-Y[i-1]
    else:
        return min(Y[i]-x, x-Y[i-1])

def near2(x, D):
    Y = [d for d ,_ in D]
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x + D[i][1]
    elif i == len(Y):
        return x-Y[i-1] + D[i-1][1]
    else:
        return min(Y[i]-x+D[i][1], x-Y[i-1]+D[i-1][1])

from bisect import *
A, B, Q = map(int, input().split())
S = []
T = []
for _ in range(A):
    S.append(int(input()))
for _ in range(B):
    T.append(int(input()))
D = []
for a in S:
    D.append((a, near(a, T)))
for b in T:
    D.append((b, near(b, S)))
D.sort(key=lambda x:x[0])
for _ in range(Q):
    x = int(input())
    print(near2(x,D))

Submission status: Time Limit Exceeded

Solution code:
def near(x, Y):
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x
    elif i == len(Y):
        return x-Y[i-1]
    else:
        return min(Y[i]-x, x-Y[i-1])

def near2(x, D):
    Y = [d for d ,_ in D]
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x + D[i][1]
    elif i == len(Y):
        return x-Y[i-1] + D[i-1][1]
    else:
        return min(Y[i]-x+D[i][1], x-Y[i-1]+D[i-1][1])

from bisect import *
A, B, Q = map(int, input().split())
S = []
T = []
for _ in range(A):
    S.append(int(input()))
for _ in range(B):
    T.append(int(input()))
S.sort()
T.sort()
D = []
for a in S:
    D.append((a, near(a, T)))
for b in T:
    D.append((b, near(b, S)))
D.sort()
for _ in range(Q):
    x = int(input())
    print(near2(x,D))

Submission status: Time Limit Exceeded

Solution code:
A,B,Q = map(int,input().split())
S = []
for i in range(A):
  temp = int(input())
  S.append(temp)
S.sort()
T = []
for i in range(B):
  temp = int(input())
  T.append(temp)
T.sort()
#print(S,T)

def jinja(x): #移動距離、神社の位置を出力
  if x <= S[0]:
    ret = [S[0]-x,0]
  elif x >= S[-1]:
    ret = [x-S[-1],A-1]
  else:
    ok = 0
    ng = A
    while abs(ok-ng) > 1:
      mid = (ok+ng)//2
      if S[mid] <= x:
        ok = mid
      else:
        ng = mid
    ret = [x - S[ok],ok,S[ng] - x,ng]
  return ret

def tera(x): #移動距離、神社の位置を出力
  if x <= T[0]:
    ret = [T[0]-x,0]
  elif x >= T[-1]:
    ret = [x-T[-1],B-1]
  else:
    ok = 0
    ng = B
    while abs(ok-ng) > 1:
      mid = (ok+ng)//2
      if T[mid] <= x:
        ok = mid
      else:
        ng = mid
    ret = [x - T[ok],ok,T[ng] - x,ng]
  return ret
      

#P = tera(100)
#print(P)
for i in range(Q):
  INPUT = int(input())
  j = jinja(INPUT)
  #print(j)
  if len(j) == 2:
    x = j[0]; loc = S[j[1]]
    jt = tera(loc)
    if len(jt) == 2:
      x += jt[0]
    else:
      x += min(jt[0],jt[2])
  else:
    x1 = j[0]; loc1 = S[j[1]]; x2 = j[2]; loc2 = S[j[3]]
    jt1 = tera(loc1); jt2 = tera(loc2)
    if len(jt1) == 2:
      x1 += jt1[0]
    else:
      x1 += min(jt1[0],jt1[2])
    if len(jt2) == 2:
      x2 += jt2[0]
    else:
      x2 += min(jt2[0],jt2[2])
    x = min(x1, x2)
  t = tera(INPUT)
  #print(t)
  if len(t) == 2:
    y = t[0]; loc = T[t[1]]
    tj = jinja(loc)
    #print(y,loc,tj)
    if len(tj) == 2:
      y += tj[0]
    else:
      y += min(tj[0],tj[2])
  else:
    y1 = t[0]; loc1 = T[t[1]]; y2 = t[2]; loc2 = T[t[3]]
    tj1 = jinja(loc1); tj2 = jinja(loc2)
    if len(tj1) == 2:
      y1 += tj1[0]
    else:
      y1 += min(tj1[0],tj1[2])
    if len(tj2) == 2:
      y2 += tj2[0]
    else:
      y2 += min(tj2[0],tj2[2])
    y = min(y1, y2)
  #print(x,y)
  print(min(x,y))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.buffer.readline

a, b, q = map(int,input().split())
ab = []
aa = []
bb = []
for i in range(a):
    x = int(input())
    ab.append([0, x])
    aa.append(x)
    
for i in range(b):
    x = int(input())
    ab.append([1, x])
    bb.append(x)
ab = sorted(ab, key=lambda x:(x[1], x[0]))

ab_arr = np.array(ab)
ab_arr = ab_arr.T[1]

a_arr = np.array(aa)
b_arr = np.array(bb)

for cq in range(q):
    ans = 10**18
    s = int(input())
    ci = np.searchsorted(ab_arr, s)
    for cj in [ci, ci-1]:
        if cj < 0 or cj >= a+b:
            continue
        d = abs(ab_arr[cj] - s)
        flg = ab[cj][0]
        if flg:
            nj = np.abs(a_arr - ab_arr[cj]).argmin()
            d += abs(a_arr[nj] - ab_arr[cj])
        else:
            nj = np.abs(b_arr - ab_arr[cj]).argmin()
            d += abs(b_arr[nj] - ab_arr[cj])
        ans = min(ans, d)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

a, b, q = map(int,input().split())
ab = []
aa = []
bb = []
for i in range(a):
    x = int(input())
    ab.append([0, x])
    aa.append(x)
    
for i in range(b):
    x = int(input())
    ab.append([1, x])
    bb.append(x)
ab = sorted(ab, key=lambda x:(x[1], x[0]))

ab_arr = np.array(ab)
ab_arr = ab_arr.T[1]

a_arr = np.array(aa)
b_arr = np.array(bb)

for cq in range(q):
    ans = 10**18
    s = int(input())
    ci = np.searchsorted(ab_arr, s)
    for cj in [ci, ci-1]:
        if cj < 0 or cj >= a+b:
            continue
        d = abs(ab_arr[cj] - s)
        flg = ab[cj][0]
        if flg:
            nj = np.abs(a_arr - ab_arr[cj]).argmin()
            d += abs(a_arr[nj] - ab_arr[cj])
        else:
            nj = np.abs(b_arr - ab_arr[cj]).argmin()
            d += abs(b_arr[nj] - ab_arr[cj])
        ans = min(ans, d)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
A, B, Q = map(int, input().split())
S = [-float('inf')] + [int(input()) for _ in range(A)] + [float('inf')]
T = [-float('inf')] + [int(input()) for _ in range(B)] + [float('inf')]
S_rev = [-s for s in S][::-1]
T_rev = [-t for t in T][::-1]

for q in range(Q):
    x = int(input())
    ans = float('inf')

    # Case1: 右に直進
    cost1_s = S[bisect_left(S, x)] - x
    cost1_t = T[bisect_left(T, x)] - x
    ans = min(ans, max(cost1_s, cost1_t))

    # Case2: 左に直進
    cost2_s = S_rev[bisect_left(S_rev, -x)] + x
    cost2_t = T_rev[bisect_left(T_rev, -x)] + x
    ans = min(ans, max(cost2_s, cost2_t))

    # Case3: 右でS、左でT
    cost3_s = S[bisect_left(S, x)] - x
    cost3_t = T_rev[bisect_left(T_rev, -x)] + x
    ans = min(ans, 2 * min(cost3_s, cost3_t) + max(cost3_s, cost3_t))

    # Case4: 右でT、左でS
    cost3_s = S_rev[bisect_left(S_rev, -x)] + x
    cost3_t = T[bisect_left(T, x)] - x
    ans = min(ans, 2 * min(cost3_s, cost3_t) + max(cost3_s, cost3_t))

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc119


def leq_search(xs, x, s, t):
    # x以下で最大のindex
    if t-s <= 3:
        res = 0
        for i in range(s, t):
            if xs[i] <= x:
                res = i
        return res

    i = (s+t)//2
    if xs[i] <= x:
        return leq_search(xs, x, i, t)
    else:
        return leq_search(xs, x, s, i)


def geq_search(xs, x, s, t):
    # x以上で最小のindex
    if t-s <= 3:
        res = 0
        for i in range(t-1, s-1, -1):
            if xs[i] >= x:
                res = i
        return res

    i = (s+t)//2
    if xs[i] >= x:
        return geq_search(xs, x, s, i+1)
    else:
        return geq_search(xs, x, i+1, t)


def nearest_search(xs, x, s, t):
    # xにもっとも近いindex
    if t-s <= 3:
        res = s
        for i in range(s, t):
            if abs(x-xs[i]) < abs(x-xs[res]):
                res = i
        return res

    i = (s+t)//2
    if xs[i] <= x:
        return nearest_search(xs, x, i, t)
    else:
        return nearest_search(xs, x, s, i+1)


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

    S, T = 0, 1
    st = [[s[i], S, i] for i in range(A)]
    st.extend([[t[i], T, i] for i in range(B)])
    # st = [[s[i], S, i] for i in range(A)].extend([[t[i], T, i] for i in range(B)])
    st = sorted(st, key=lambda x: x[0])
    st_retrieval = [x[0] for x in st]

    # 各神社から最寄りの寺を求める
    s_near_t = [None] * A
    for i in range(A):
        s_near_t[i] = t[nearest_search(t, s[i], 0, B)]

    # 各寺から最寄りの神社を求める
    t_near_s = [None] * B
    for i in range(B):
        t_near_s[i] = s[nearest_search(s, t[i], 0, A)]

    for x in xs:
        # left
        near_i = leq_search(st_retrieval, x, 0, A+B)
        val, mark, i = st[near_i]
        # val: 座標
        # mark: S or T
        # i: 元の列 s or t の中での index
        cand1 = abs(val-x)
        if mark == S:
            near_t = s_near_t[i]
            cand1 += abs(near_t-val)
        else:
            near_s = t_near_s[i]
            cand1 += abs(near_s-val)

        # right
        near_i = geq_search(st_retrieval, x, 0, A+B)
        val, mark, i = st[near_i]
        # val: 座標
        # mark: S or T
        # i: 元の列 s or t の中での index
        cand2 = abs(val-x)
        if mark == S:
            near_t = s_near_t[i]
            cand2 += abs(near_t-val)
        else:
            near_s = t_near_s[i]
            cand2 += abs(near_s-val)
        
        print(min(cand1, cand2))


main()
# print(main())

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]
t = [int(input()) for _ in range(B)]

s.sort()
t.sort()

for k in range(Q):
    x = int(input())
    ans = []
    ms = bisect_left(s, x)
    for i in [-1, 0, 1]:
        if 0 <= ms + i <= A - 1:
            mt = bisect_left(t, s[ms + i])
            for j in [-1, 0, 1]:
                if 0 <= mt + j <= B - 1:
                    ans.append(abs(s[ms + i] - x) + abs(t[mt + j] - s[ms + i]))
    mt = bisect_left(t, x)
    for i in [-1, 0, 1]:
        if 0 <= mt + i <= B - 1:
            ms = bisect_left(s, t[mt + i])
            for j in [-1, 0, 1]:
                if 0 <= ms + j <= A - 1:
                    ans.append(abs(t[mt + i] - x) + abs(s[ms + j] - t[mt + i]))
    print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import math

a, b, q = map(int, input().split())
s = [-math.inf]
t = [-math.inf]
x = []
for _ in range(a):
    s.append(int(input()))
for _ in range(b):
    t.append(int(input()))
for _ in range(q):
    x.append(int(input()))
s.append(math.inf)
t.append(math.inf)

import numpy as np
for i in x:
    #s->t
    st = np.nanmin(np.array([abs(s[bisect.bisect(s, i)] - i) + abs(s[bisect.bisect(s, i)] - t[bisect.bisect(t, i)]), \
             abs(s[bisect.bisect(s, i)-1] - i) + abs(s[bisect.bisect(s, i)-1] - t[bisect.bisect(t, i)]), \
             abs(s[bisect.bisect(s, i)] - i) + abs(s[bisect.bisect(s, i)] - t[bisect.bisect(t, i)-1]), \
             abs(s[bisect.bisect(s, i)-1] - i) + abs(s[bisect.bisect(s, i)-1] - t[bisect.bisect(t, i)-1])]))
    #t->s
    ts = np.nanmin(np.array([abs(t[bisect.bisect(t, i)] - i) + abs(t[bisect.bisect(t, i)] - s[bisect.bisect(s, i)]), \
             abs(t[bisect.bisect(t, i)-1] - i) + abs(t[bisect.bisect(t, i)-1] - s[bisect.bisect(s, i)]), \
             abs(t[bisect.bisect(t, i)] - i) + abs(t[bisect.bisect(t, i)] - s[bisect.bisect(s, i)-1]), \
             abs(t[bisect.bisect(t, i)-1] - i) + abs(t[bisect.bisect(t, i)-1] - s[bisect.bisect(s, i)-1])]))
    print(int(min(st, ts)))

Submission status: Time Limit Exceeded

Solution code:
a, b, q = map(int, input().split())
s = []
t = []
x = []
for _ in range(a):
    s.append(int(input()))
for _ in range(b):
    t.append(int(input()))
for _ in range(q):
    x.append(int(input()))
    
import numpy as np
s = np.array(s)
t = np.array(t)

for i in x:
    ans_st = 0
    ans_ts = 0
    # s -> t
    ans_st += min(abs(s-i))
    ans_st += min(abs(t - s[list(abs(s-i)).index(min(abs(s-i)))]))
    
    # t->s
    ans_ts += min(abs(t-i))
    ans_ts += min(abs(s - t[list(abs(t-i)).index(min(abs(t-i)))]))
    
    print(min(ans_st, ans_ts))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
A, B, Q = map(int, input().split())
S = [-(10 ** 30)] + [int(input()) for i in range(A)] + [10 ** 30]
T = [-(10 ** 30)] + [int(input()) for i in range(B)] + [10 ** 30]

INF = 10 ** 15
for i in range(Q):
    x = int(input())
    sx = bisect_left(S, x)
    tx = bisect_left(T, x)
    ans = INF
    # 4パターン試す
    for t in (T[tx-1], T[tx]):
        for s in (S[sx-1], S[sx]):
            ans = min(ans, min(abs(x-s),abs(x-t))+abs(t-s))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
A, B, Q = map(int, input().split())
S = [-(10 ** 30)] + [int(input()) for i in range(A)] + [10 ** 30]
T = [-(10 ** 30)] + [int(input()) for i in range(B)] + [10 ** 30]

INF = 10 ** 15
for i in range(Q):
    x = int(input())
    sx = bisect_left(S, x)
    tx = bisect_left(T, x)
    ans = INF
    # 4パターン試す
    for t in T[tx-1:tx+1]:
        for s in S[sx-1:sx+1]:
            ans = min(ans, min(abs(x-s),abs(x-t))+abs(t-s))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
A, B, Q = map(int, input().split())
S = [-(10 ** 30)] + [int(input()) for i in range(A)] + [10 ** 30]
T = [-(10 ** 30)] + [int(input()) for i in range(B)] + [10 ** 30]

for i in range(Q):
    x = int(input())
    sx = bisect_left(S, x)
    tx = bisect_left(T, x)
    ans = 10 ** 30
    # 4パターン試す
    for t in T[tx-1:tx+1]:
        for s in S[sx-1:sx+1]:
            ans = min(ans, abs(x-t)+abs(t-s))
            ans = min(ans, abs(x-s)+abs(t-s))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
A, B, Q = map(int, input().split())
S = [-(10 ** 30)] + [int(input()) for i in range(A)] + [10 ** 30]
T = [-(10 ** 30)] + [int(input()) for i in range(B)] + [10 ** 30]

for i in range(Q):
    x = int(input())
    sx = bisect_left(S, x)
    tx = bisect_left(T, x)
    ans = 10 ** 30
    # 4パターン試す
    ans = min(ans, min(abs(x-S[sx-1])+abs(S[sx-1]-T[tx]), abs(T[tx]-S[sx-1])+abs(x-T[tx])))
    ans = min(ans, max(abs(x-S[sx-1]),abs(x-T[tx-1])))
    ans = min(ans, max(abs(x-S[sx]),abs(x-T[tx])))
    ans = min(ans, min(abs(x-S[sx])+abs(S[sx]-T[tx-1]), abs(T[tx-1]-S[sx])+abs(x-T[tx-1])))
    
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

a, b, q = map(int, input().split())

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

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

for i in range(q):
    x = int(input())
    ps = bisect.bisect_right(s, x)
    pt = bisect.bisect_right(t, x)
    ret = 10 ** 19
    for loc1 in (s[ps], s[ps-1]):
        for loc2 in (t[pt], t[pt-1]):
            val = min(abs(x-loc1) + abs(loc1-loc2),
                      abs(x-loc2) + abs(loc1-loc2))
            ret = min(ret, val)
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
import bisect
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:
    SL, SR, TL, TR = 10**20, 10**20, 10**20, 10**20
    i = bisect.bisect_left(S, x)
    if i != 0:
        SL = x-S[i-1]
    if i != A:
        SR = S[i]-x

    j = bisect.bisect_left(T, x)
    if j != 0:
        TL = x-T[j-1]
    if j != B:
        TR = T[j]-x

    ans = min(max(SL, TL), min(2*SL+TR, SL+2*TR),
              min(2*TL+SR, TL+2*SR), max(SR, TR))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
A,B,Q=map(int, input().split())
from bisect import bisect_left

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

for i in range(Q):
    x=int(input())
    sidx=bisect_left(S, x)
    tidx=bisect_left(T, x)
    if 0<=sidx<A and 0<=tidx<B:
        a1=max(S[sidx], T[tidx])-x
    else:
        a1=float("INF")
    if 0<=sidx-1<A and 0<=tidx-1<B:
        a2=max(x-S[sidx-1], x-T[tidx-1])
    else:
        a2=float("INF")
    if 0<=sidx<A and 0<=tidx-1<B:
        a3=S[sidx]-T[tidx-1]+min(S[sidx]-x, x-T[tidx-1])
    else:
        a3=float("INF")
    if 0<=sidx-1<A and 0<=tidx<B:
        a4=T[tidx]-S[sidx-1]+min(T[tidx]-x, x-S[sidx-1])
    else:
        a4=float("INF")
    #print(a1,a2,a3,a4)
    ans=min(a1,a2,a3,a4)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
A, B, Q = map(int,input().split())
s = [-10**20] + [int(input()) for k in range(A)] + [10**20,10**20]
t = [-10**20] + [int(input()) for k in range(B)] + [10**20,10**20]

for _ in range(Q):
    x = int(input())
    print(min(
        max(s[bisect.bisect_left(s,x)],t[bisect.bisect_left(t,x)])-x,
        x-min(s[bisect.bisect_left(s,x)-1],t[bisect.bisect_left(t,x)-1]),
        s[bisect.bisect_left(s,x)]-x + s[bisect.bisect_left(s,x)]-t[bisect.bisect_left(t,x)-1],
        t[bisect.bisect_left(t,x)]-x + t[bisect.bisect_left(t,x)]-s[bisect.bisect_left(s,x)-1],
        x-s[bisect.bisect_left(s,x)-1] + t[bisect.bisect_left(t,x)]-s[bisect.bisect_left(s,x)-1],
        x-t[bisect.bisect_left(t,x)-1] + s[bisect.bisect_left(s,x)]-t[bisect.bisect_left(t,x)-1]))

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    a,b,q = LI()
    sa = [-inf] + [I() for _ in range(a)] + [inf, inf]
    ta = [-inf] + [I() for _ in range(b)] + [inf, inf]
    xa = [I() for _ in range(q)]
    r = []
    for x in xa:
        si = bisect.bisect_left(sa, x)
        ti = bisect.bisect_left(ta, x)
        t = inf
        k = x - sa[si-1]
        for i in range(ti,-1,-1):
            u = k + abs(sa[si-1] - ta[i])
            if t > u:
                t = u
            if ta[i] <= sa[si-1]:
                break

        k = sa[si] - x
        for i in range(ti-1,b+2):
            u = k + abs(sa[si] - ta[i])
            if t > u:
                t = u
            if ta[i] >= sa[si]:
                break

        k = x - ta[ti-1]
        for i in range(si,-1,-1):
            u = k + abs(ta[ti-1] - sa[i])
            if t > u:
                t = u
            if sa[i] <= ta[ti-1]:
                break

        k = ta[ti] - x
        for i in range(si-1,a+2):
            u = k + abs(ta[ti] - sa[i])
            if t > u:
                t = u
            if sa[i] >= ta[ti]:
                break

        r.append(t)

    return JA(r, "\n")

print(main())

Submission status: Time Limit Exceeded

Solution code:
def find_min_fuka_idx(lst, x):
  ok = -1
  ng = len(lst)
  while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if x>=lst[mid]:
      ok = mid
    else:
      ng = mid
  return ng

a,b,q = map(int, input().split())
s = [-10**18]
s_mid = [int(input()) for i in range(a)]
s.extend(s_mid)
s.append(10**18)
  
t = [-10**18]
t_mid = [int(input()) for i in range(b)]
t.extend(t_mid)
t.append(10**18)

for i in range(q):
  x = int(input())
  si = find_min_fuka_idx(s, x)
  tj = find_min_fuka_idx(t, x)
  ssi = s[si]
  ssi1 = s[si-1]
  ttj = t[tj]
  ttj1 = t[tj-1]
  print(min(abs(x-ssi)+abs(ssi-ttj),\
            abs(x-ssi)+abs(ssi-ttj1),\
           abs(x-ttj)+abs(ttj-ssi),\
            abs(x-ttj)+abs(ttj-ssi1),\
            abs(x-ssi1)+abs(ssi1-ttj),\
            abs(x-ssi1)+abs(ssi1-ttj1),\
           abs(x-ttj1)+abs(ttj1-ssi),\
            abs(x-ttj1)+abs(ttj1-ssi1)))

Submission status: Time Limit Exceeded

Solution code:
def find_min_fuka_idx(lst, x):
  ok = -1
  ng = len(lst)
  while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if x>=lst[mid]:
      ok = mid
    else:
      ng = mid
  return ng

a,b,q = map(int, input().split())
s = [-10**18]
s_mid = [int(input()) for i in range(a)]
s.extend(s_mid)
s.append(10**18)

t = [-10**18]
t_mid = [int(input()) for i in range(b)]
t.extend(t_mid)
t.append(10**18)

for i in range(q):
  x = int(input())
  si = find_min_fuka_idx(s, x)
  tj = find_min_fuka_idx(t, x)
  print(min(abs(x-s[si])+abs(s[si]-t[tj]),\
            abs(x-s[si])+abs(s[si]-t[tj-1]),\
           abs(x-t[tj])+abs(t[tj]-s[si]),\
            abs(x-t[tj])+abs(t[tj]-s[si-1]),\
            abs(x-s[si-1])+abs(s[si-1]-t[tj]),\
            abs(x-s[si-1])+abs(s[si-1]-t[tj-1]),\
           abs(x-t[tj-1])+abs(t[tj-1]-s[si]),\
            abs(x-t[tj-1])+abs(t[tj-1]-s[si-1])))

Submission status: Time Limit Exceeded

Solution code:
def find_min_fuka_idx(lst, x):
  ok = -1
  ng = len(lst)
  while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if x>=lst[mid]:
      ok = mid
    else:
      ng = mid
  return ng

a,b,q = map(int, input().split())
s = [-10**18]
for i in range(a):
  s.append(int(input()))
s.append(10**18)
t = [-10**18]
for i in range(b):
  t.append(int(input()))
t.append(10**18)

for i in range(q):
  x = int(input())
  si = find_min_fuka_idx(s, x)
  tj = find_min_fuka_idx(t, x)
  print(min(abs(x-s[si])+abs(s[si]-t[tj]),\
            abs(x-s[si])+abs(s[si]-t[tj-1]),\
           abs(x-t[tj])+abs(t[tj]-s[si]),\
            abs(x-t[tj])+abs(t[tj]-s[si-1]),\
            abs(x-s[si-1])+abs(s[si-1]-t[tj]),\
            abs(x-s[si-1])+abs(s[si-1]-t[tj-1]),\
           abs(x-t[tj-1])+abs(t[tj-1]-s[si]),\
            abs(x-t[tj-1])+abs(t[tj-1]-s[si-1])))

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
input = sys.stdin.readline
A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]
t = [int(input()) for _ in range(B)]
s = sorted(s)
t = sorted(t)

for _ in range(Q):
    x = int(input())
    idx1 = bisect.bisect_right(s, x)
    idx2 = bisect.bisect_right(t, x)
    ans = float('inf')
    if idx1 > 0:
        left_s = s[idx1-1]
    else:
        left_s = float('inf')
    if idx2 > 0:
        left_t = t[idx2-1]
    else:
        left_t = float('inf')
    if idx1 < A:
        right_s = s[idx1]
    else:
        right_s = float('inf')
    if idx2 < B:
        right_t = t[idx2]
    else:
        right_t = float('inf')

    ls = x-left_s
    lt = x-left_t
    rs = right_s-x
    rt = right_t-x 
    if left_s <= x <= right_t:
        tmp = right_t-left_s + min(ls, rt)
        ans = min(ans, tmp)
    if left_t <= x <= right_s:
        tmp = right_s-left_t + min(lt, rs)
        ans = min(ans, tmp)
    ans = min(ans, max(abs(ls), abs(lt)))
    ans = min(ans, max(abs(rs), abs(rt)))
    print(ans)