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:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

a,b,q=acinput()

S=[]
for i in range(a):
    S.append(II())

T=[]
for i in range(b):
    T.append(II())

#X=[II() for i in range(q)]

import bisect

for i in range(q):
    x=II()

    t=bisect.bisect(S,x)
    t=min(t,a-1)
    d1=abs(S[t]-x)
    t2=bisect.bisect(T,S[t])
    t2=min(t2,b-1)
    d2=abs(T[t2]-S[t])

    res=d1+d2

    t = bisect.bisect(T, x)
    t = min(t, b-1)
    d1 = abs(T[t]-x)
    t2 = bisect.bisect(S,T[t])
    t2 = min(t2, a-1)
    d2 = abs(S[t2]-T[t])
    res=min(res,d1+d2)
    print(res)

Submission status: Wrong Answer

Solution code:
from bisect import *
A,B,Q=map(int,input().split())
S=[int(input()) for i in range(A)]
T=[int(input()) for i in range(B)]
value1=2*(10**10)
for zzz in range(Q):
    x=int(input())
    value=value1
    s1=bisect_left(S,x)
    for s in [s1-1,s1]:
        if -1< s < A:
            t1=bisect_left(T,S[s])
            for t in [t1-1,t1]:
                a=0
                if -1< t < B:
                    if x>S[s]:
                        a+=x-S[s]
                    else:
                        a+=S[s]-x
                    if S[s]>T[t]:
                        a+=S[s]-T[t]
                    else:
                        a+=T[t]-S[s]
                    if value>a:
                        value=a
    """t1=bisect_left(T,x)
    for t in [t1-1,t1]:
        if -1< t < B:
            s1=bisect_left(S,T[t])
            for s in [s1-1,s1]:
                a=0
                if -1< s < A:
                    if x>T[t]:
                        a+=x-T[t]
                    else:
                        a+=T[t]-x
                    if S[s]>T[t]:
                        a+=S[s]-T[t]
                    else:
                        a+=T[t]-S[s]
                    if value>a:
                        value=a"""

    print(value)

Submission status: Wrong Answer

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999999
R = 10**9 + 7
import bisect

def ddprint(x):
  if DBG:
    print(x)

a,b,q = inm()
s = []
t = []
for i in range(a):
    s.append(inn())
for i in range(b):
    t.append(inn())
for qq in range(q):
    x = inn()
    mn = BIG

    i = bisect.bisect_left(s,x)
    j = bisect.bisect_left(t,x)
    #ddprint("i {} j {}".format(i,j))
    if i>0 and j>0:
        mn = min(mn, x-min(s[i-1],t[j-1]))
    if i>0 and j<b:
        mn = min(mn, min(x-s[i-1],t[j]-x)+t[j]-s[i-1])
    if i<a-1 and j>0:
        mn = min(mn, min(x-t[j-1],s[i]-x)+s[i]-t[j-1])
    if i<a-1 and j<b:
        mn = min(mn, max(s[i],t[j])-x)
    print(mn)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
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)])
X = [int(input()) for i in range(Q)]


for x in X:
  s_index = bisect_left(S, x)
  s_left = S[s_index - 1] if s_index > 0 else None
  s_right = S[s_index] if s_index < A else None
  t_index = bisect_left(T, x)
  t_left = T[t_index - 1] if t_index > 0 else None
  t_right = T[t_index] if t_index < B else None

  ans = float("inf")

  sl = [s_left, s_left]
  tl = [t_left, t_right]

  for s in sl:
    if not s: continue
    for t in tl:
      if not t: continue
      ans = min(ans, abs(x-s) + abs(t-s))

  for t in tl:
    if not t: continue
    for s in sl:
      if not s: continue
      ans = min(ans, abs(x-t) + abs(t-s)) 

  print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
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:
  s_index = bisect_left(S, x)
  s_left = S[s_index - 1] if s_index > 0 else None
  s_right = S[s_index] if s_index < A else None
  t_index = bisect_left(T, x)
  t_left = T[t_index - 1] if t_index > 0 else None
  t_right = T[t_index] if t_index < B else None

  ans = float("inf")

  sl = [s_left, s_left]
  tl = [t_left, t_right]

  for s in sl:
    if not s: continue
    for t in tl:
      if not t: continue
      ans = min(ans, abs(x-s) + abs(t-s))

  for t in tl:
    if not t: continue
    for s in sl:
      if not s: continue
      ans = min(ans, abs(x-t) + abs(t-s)) 

  print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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


for q_i in range(q):
  x_pos_s = bisect.bisect_left(S, X[q_i])
  x_pos_t = bisect.bisect_left(T, X[q_i])
  
  pos_0 = min(S[x_pos_s-1], T[x_pos_t-1])
  pos_1 = max(S[x_pos_s-1], T[x_pos_t-1])
  pos_2 = min(S[x_pos_s], T[x_pos_t])
  pos_3 = max(S[x_pos_s], T[x_pos_t])
  
  ans = min(abs(X[q_i]-pos_0),
            abs(X[q_i]-pos_3),
            abs(pos_2-pos_1)+min(abs(X[q_i]-pos_1),abs(X[q_i]-pos_2)))
  
  print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.readline

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

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

for i in range(B):
    t[i]=int(input())
    
#神社/寺から最寄りの寺/神社のインデックスを記憶
ns=[0]*A
nt=[0]*B

def bi_se(L,x):
    k=bisect.bisect_left(L,x)
    if k==len(L):
        return k-1
    d1=abs(x-L[k])
    d2=abs(x-L[k-1])
    kk=k
    if d2<d1:
        kk=k-1
    return kk
    

for i in range(A):
    ns[i]=bi_se(t,s[i])
    
for i in range(B):
    nt[i]=bi_se(s,t[i])
    
for i in range(Q):
    x=int(input())
    ai=bi_se(s,x)
    la=abs(x-s[ai])+abs(s[ai]-t[ns[ai]])
    
    bi=bi_se(t,x)
    lb=abs(x-t[bi])+abs(t[bi]-s[nt[bi]])
    print(min(la,lb))

Submission status: Wrong Answer

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

for _ in range(q):
    x = int(input())
    # print('x', x)
    ss = bisect(s, x)
    tt = bisect(t, x)
    tmp = []
    if ss > 0 and tt > 0:
        i = abs(s[ss-1] - x)
        j = abs(t[tt-1] - x)
        if s[ss-1] <= x <= t[tt-1] or s[ss-1] >= x >= t[tt-1]:
            # print(i+j+min(i,j), s[ss-1], t[tt-1])
            tmp.append(i+j+min(i,j))
        else:
            # print((i-j), s[ss-1], t[tt-1])
            tmp.append(max(i,j))
    if 0 < ss and tt < b:
        i = abs(s[ss-1] - x)
        j = abs(t[tt] - x)
        if s[ss-1] <= x <= t[tt] or s[ss-1] >= x >= t[tt]:
            tmp.append(i+j+min(i,j))
        else:
            tmp.append(max(i,j))
    if ss == 0 and tt > 0:
        i = abs(s[ss] - x)
        j = abs(t[tt-1] - x)
        if s[ss] <= x <= t[tt-1] or s[ss] >= x >= t[tt-1]:
            # print(i+j+min(i,j), s[ss], t[tt-1])
            tmp.append(i+j+min(i,j))
        else:
            # print(i-j, s[ss], t[tt-1])
            tmp.append(max(i,j))
    if ss < a and tt < b:
        i = abs(s[ss] - x)
        j = abs(t[tt] - x)
        if s[ss] <= x <= t[tt] or s[ss] >= x >= t[tt]:
            # print(i+j+min(i,j), s[ss], t[tt])
            tmp.append(i+j+min(i,j))
        else:
            # print(i-j, s[ss], t[tt])
            tmp.append(max(i,j))
    # print(tmp, ss, tt)
    print(min(tmp))

Submission status: Wrong Answer

Solution code:
import bisect
A, B, Q = map(int, input().split())  # A個の神社, B個の寺, Q個のクエリ
INF = 10 ** 18
shrines = [-INF] + [int(input()) for _ in range(A)] + [INF]
temples = [-INF] + [int(input()) for _ in range(B)] + [INF]
X = [int(input()) for _ in range(Q)]

# bisect.bisect_left(list, value)  # value以上が初めて現れるインデックスを返す
# bisect.bisect_right(list, value)  # valueより真に大きい値が初めて現れるインデックスを返す, こっちを使う, index-1で左側が取れる

shrines.sort()  # 神社
temples.sort()  # 寺
for x in X:
    tmp = 10**18

    s_right_index = bisect.bisect_right(shrines, x)  # 右側の神社
    s_left_index = bisect.bisect_right(shrines, x)-1  # 左側の神社
    t_right_index = bisect.bisect_right(temples, x)  # 右側の寺
    t_left_index = bisect.bisect_right(temples, x)-1  # 左側の寺

    # 右側だけを訪れる, 遠い方の値だけで良い
    tmp = min(tmp, max(shrines[s_right_index], temples[t_right_index])-x)

    # 右の神社に行って、左側の寺に行く
    tmp = min(tmp, abs((shrines[s_right_index]-x)) * 2 + abs(temples[t_left_index]))

    # 右の寺に行って、左側の神社に行く
    tmp = min(tmp, abs((temples[t_right_index]-x)) * 2 + abs(shrines[s_left_index]))

    # 左の寺に行って、右の神社に行く
    tmp = min(tmp, abs((temples[t_left_index]-x)) * 2 + abs(shrines[s_right_index]))

    # 左の神社に行って、右の寺に行く
    tmp = min(tmp, abs((shrines[s_left_index]-x)) * 2 + abs(temples[t_left_index]))

    # 左側だけを訪れる
    tmp = min(tmp, abs(x - min(abs(shrines[s_left_index]), abs(temples[t_left_index]))))

    print(tmp)

Submission status: Wrong Answer

Solution code:
import bisect

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



for i in range(q):
    x = int(input())
    xs = bisect.bisect_right(s,x)
    xt = bisect.bisect_right(t,x)
    ss = [x-s[xs-1],s[xs]-x]
    tt = [x-t[xt-1],t[xt]-x]
    print(min(max(ss[0],tt[0]), max(ss[1],tt[1])))

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
input = sys.stdin.readline
INF = 10**18
a, b, q = map(int, input().split())
S = [-INF] + [ int(input()) for _ in range(a) ] + [INF]
T = [-INF] + [ int(input()) for _ in range(b) ] + [INF]

for i in range(q):
    x = int(input())
    c, d = bisect_left(S, x), bisect_left(T, x)
    ans = INF
    for s in S[c:c+2]:
        for t in T[d:d+2]:
            ans = min( ans, abs(t-x)+abs(s-t), abs(s-x)+abs(t-s) )
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
input = sys.stdin.readline
INF = 10**9
a, b, q = map(int, input().split())
S = [-INF] + [ int(input()) for _ in range(a) ] + [INF]
T = [-INF] + [ int(input()) for _ in range(b) ] + [INF]

for i in range(q):
    x = int(input())
    c, d = bisect_left(S, x), bisect_left(T, x)
    ans = INF
    for s in S[c:c+2]:
        for t in T[d:d+2]:
            ans = min( ans, abs(t-x)+abs(s-t), abs(s-x)+abs(t-s) )
    print(ans)

Submission status: Wrong Answer

Solution code:
INF = 10**18

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

from bisect import bisect_left

for x in X:
    # xに一番近い神社に行く
    res1 = 0
    shrine = bisect_left(s,x)
    tmp1 = s[shrine] if abs(s[shrine] - x) <= abs(s[shrine-1] - x) else s[shrine-1]
    res1 += abs(tmp1 - x)
    tmp2 = tmp1
    temple = bisect_left(t,tmp2)
    tmp1 = t[temple] if abs(t[temple] - tmp2) <= abs(t[temple-1] - tmp2) else t[temple-1]
    res1 += abs(tmp1 - tmp2)

    # xに一番近い寺に行く
    res2 = 0
    temple = bisect_left(t,x)
    tmp1 = t[temple] if abs(t[temple] - x) <= abs(t[temple-1] - x) else t[temple-1]
    res2 += abs(tmp1 - x)
    tmp2 = tmp1
    shrine = bisect_left(s,tmp2)
    tmp1 = s[shrine] if abs(s[shrine] - tmp2) <= abs(s[shrine-1] - tmp2) else s[shrine-1]
    res2 += abs(tmp1 - tmp2)

    print(min(res1,res2))

Submission status: Wrong Answer

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

def bin_search(a, x):
    n = len(a)
    l, r = -1, n
    while r - l > 1:
        i = (l + r) // 2
        if a[i] >= x: r = i
        else: l = i
    return None if l == -1 else a[l], None if r == n else a[r]

for _ in range(q):
    x = int(input())
    dists = []
    for p1 in bin_search(s, x):
        if p1 == None: continue
        d = abs(p1 - x)
        for p2 in bin_search(t, x):
            if p2 == None: continue
            d += abs(p2 - p1)
            dists.append(d)
    for p1 in bin_search(t, x):
        if p1 == None: continue
        d = abs(p1 - x)
        for p2 in bin_search(s, x):
            if p2 == None: continue
            d += abs(p2 - p1)
            dists.append(d)
    print(min(dists))

Submission status: Wrong Answer

Solution code:
import bisect
a,b,q=map(int,input().split())
A=[-10**11]
for i in range(a):
  A.append(int(input()))
A.append(10**11)
print(A)
B=[-10**11]
for i in range(b):
  B.append(int(input()))
B.append(10**11)
for i in range(q):
  x=int(input())
  c=bisect.bisect_left(A,x,hi=len(A))
  print(c)
  d=bisect.bisect_left(B,x,hi=len(B))
  ans=min(abs(A[c-1]-x)+abs(B[d-1]-A[c-1]),abs(A[c-1]-x)+abs(B[d]-A[c-1]),abs(A[c]-x)+abs(B[d-1]-A[c]),abs(A[c]-x)+abs(B[d]-A[c]),abs(B[d-1]-x)+abs(B[d-1]-A[c-1]),abs(B[d-1]-x)+abs(B[d-1]-A[c]),abs(B[d]-x)+abs(B[d]-A[c-1]),abs(B[d]-x)+abs(B[d]-A[c]))
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import bisect


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    a, b, q = list(map(int, readline().split()))
    s = [int(readline()) for _ in range(a)]
    t = [int(readline()) for _ in range(b)]
    x = [int(readline()) for _ in range(q)]
    for xv in x:
        sp = bisect.bisect_left(s, xv)
        tp = bisect.bisect_left(t, xv)
        ss = s[sp] if sp == 0 else 10 ** 10 if sp == len(s) else s[sp-1]
        ss -= xv
        se = 10 ** 10 if sp == 0 else s[sp-1] if sp == len(s) else s[sp]
        se -= xv
        ts = t[tp] if tp == 0 else 10 ** 10 if tp == len(t) else t[tp-1]
        ts -= xv
        te = 10 ** 10 if tp == 0 else t[tp-1] if tp == len(t) else t[tp]
        te -= xv
        mt = 10 ** 10
        for sv in [ss, se]:
            for tv in [ts, te]:
                if sv * tv < 0:
                    mt = min(mt, abs(sv) + abs(tv) + min(abs(sv), abs(tv)))
                else:
                    mt = min(mt, max(abs(sv), abs(tv)))
        print(mt)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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 i in range(q):
    #ans
    if 0 <= bisect.bisect_left(s, x[i]) - 1 <= a - 1 and 0 <= bisect.bisect_left(s, x[i]) <= a - 1 :
        tmp1 = s[bisect.bisect_left(s, x[i]) - 1]
        tmp2 = s[bisect.bisect_left(s, x[i])]
        # tmp1
        if 0 <= bisect.bisect_left(t, tmp1) - 1 <= b - 1 and 0 <= bisect.bisect_left(t, tmp1) <= b - 1 :
            tmp11 = t[bisect.bisect_left(t, tmp1) - 1]
            tmp12 = t[bisect.bisect_left(t, tmp1)]
            ans1 = min(abs(x[i] - tmp1) + abs(tmp1 - tmp11), abs(x[i] - tmp1) + abs(tmp1 - tmp12))
        elif 0 <= bisect.bisect_left(t, tmp1) - 1 <= b - 1:
            tmp11 = t[bisect.bisect_left(t, tmp1) - 1]
            ans1 = abs(x[i] - tmp1) + abs(tmp1 - tmp11)
        elif 0 <= bisect.bisect_left(t, tmp1) <= b - 1:
            tmp12 = t[bisect.bisect_left(t, tmp1)]
            ans1 = abs(x[i] - tmp1) + abs(tmp1 - tmp12)
        #tmp2
        if 0 <= bisect.bisect_left(t, tmp2) - 1 <= b - 1 and 0 <= bisect.bisect_left(t, tmp2) <= b - 1 :
            tmp21 = t[bisect.bisect_left(t, tmp2) - 1]
            tmp22 = t[bisect.bisect_left(t, tmp2)]
            ans2 = min(abs(x[i] - tmp2) + abs(tmp2 - tmp21), abs(x[i] - tmp2) + abs(tmp2 - tmp22))
        elif 0 <= bisect.bisect_left(t, tmp2) - 1 <= b - 1:
            tmp21 = t[bisect.bisect_left(t, tmp2) - 1]
            ans2 = abs(x[i] - tmp2) + abs(tmp2 - tmp21)
        elif 0 <= bisect.bisect_left(t, tmp2) <= b - 1:
            tmp22 = t[bisect.bisect_left(t, tmp2)]
            ans2 = abs(x[i] - tmp2) + abs(tmp2 - tmp22)
        
        ans = min(ans1, ans2)

    elif 0 <= bisect.bisect_left(s, x[i]) - 1 <= a - 1:
        tmp1 = s[bisect.bisect_left(s, x[i]) - 1]
        #print('tmp1', tmp1)
        # tmp1
        if 0 <= bisect.bisect_left(t, tmp1) - 1 <= b - 1 and 0 <= bisect.bisect_left(t, tmp1) <= b - 1 :
            tmp11 = t[bisect.bisect_left(t, tmp1) - 1]
            tmp12 = t[bisect.bisect_left(t, tmp1)]
            ans1 = min(abs(x[i] - tmp1) + abs(tmp1 - tmp11), abs(x[i] - tmp1) + abs(tmp1 - tmp12))
        elif 0 <= bisect.bisect_left(t, tmp1) - 1 <= b - 1:
            tmp11 = t[bisect.bisect_left(t, tmp1) - 1]
            ans1 = abs(x[i] - tmp1) + abs(tmp1 - tmp11)
        elif 0 <= bisect.bisect_left(t, tmp1) <= b - 1:
            tmp12 = t[bisect.bisect_left(t, tmp1)]
            ans1 = abs(x[i] - tmp1) + abs(tmp1 - tmp12)
        
        ans =  ans1
    
    elif 0 <= bisect.bisect_left(s, x[i]) <= a - 1 :
        tmp2 = s[bisect.bisect_left(s, x[i])]
        #tmp2
        if 0 <= bisect.bisect_left(t, tmp2) - 1 <= b - 1 and 0 <= bisect.bisect_left(t, tmp2) <= b - 1 :
            tmp21 = t[bisect.bisect_left(t, tmp2) - 1]
            tmp22 = t[bisect.bisect_left(t, tmp2)]
            ans2 = min(abs(x[i] - tmp2) + abs(tmp2 - tmp21), abs(x[i] - tmp2) + abs(tmp2 - tmp22))
        elif 0 <= bisect.bisect_left(t, tmp2) - 1 <= b - 1:
            tmp21 = t[bisect.bisect_left(t, tmp2) - 1]
            ans2 = abs(x[i] - tmp2) + abs(tmp2 - tmp21)
        elif 0 <= bisect.bisect_left(t, tmp2) <= b - 1:
            tmp22 = t[bisect.bisect_left(t, tmp2)]
            ans2 = abs(x[i] - tmp2) + abs(tmp2 - tmp22)
        
        ans = ans2

    #anss
    if 0 <= bisect.bisect_left(t, x[i]) - 1 <= b - 1 and 0 <= bisect.bisect_left(t, x[i]) <= b - 1 :
        tmp1 = t[bisect.bisect_left(t, x[i]) - 1]
        tmp2 = t[bisect.bisect_left(t, x[i])]
        # tmp1
        if 0 <= bisect.bisect_left(s, tmp1) - 1 <= a - 1 and 0 <= bisect.bisect_left(s, tmp1) <= a - 1 :
            tmp11 = s[bisect.bisect_left(s, tmp1) - 1]
            tmp12 = s[bisect.bisect_left(s, tmp1)]
            ans1 = min(abs(x[i] - tmp1) + abs(tmp1 - tmp11), abs(x[i] - tmp1) + abs(tmp1 - tmp12))
        elif 0 <= bisect.bisect_left(s, tmp1) - 1 <= a - 1:
            tmp11 = s[bisect.bisect_left(s, tmp1) - 1]
            ans1 = abs(x[i] - tmp1) + abs(tmp1 - tmp11)
        elif 0 <= bisect.bisect_left(s, tmp1) <= a - 1:
            tmp12 = s[bisect.bisect_left(s, tmp1)]
            ans1 = abs(x[i] - tmp1) + abs(tmp1 - tmp12)
        #tmp2
        if 0 <= bisect.bisect_left(s, tmp2) - 1 <= a - 1 and 0 <= bisect.bisect_left(s, tmp2) <= a - 1 :
            tmp21 = s[bisect.bisect_left(s, tmp2) - 1]
            tmp22 = s[bisect.bisect_left(s, tmp2)]
            ans2 = min(abs(x[i] - tmp2) + abs(tmp2 - tmp21), abs(x[i] - tmp2) + abs(tmp2 - tmp22))
        elif 0 <= bisect.bisect_left(s, tmp2) - 1 <= a - 1:
            tmp21 = s[bisect.bisect_left(s, tmp2) - 1]
            ans2 = abs(x[i] - tmp2) + abs(tmp2 - tmp21)
        elif 0 <= bisect.bisect_left(s, tmp2) <= a - 1:
            tmp22 = t[bisect.bisect_left(s, tmp2)]
            ans2 = abs(x[i] - tmp2) + abs(tmp2 - tmp22)
        
        anss = min(ans1, ans2)

    elif 0 <= bisect.bisect_left(t, x[i]) - 1 <= b - 1:
        tmp1 = t[bisect.bisect_left(t, x[i]) - 1]
        # tmp1
        if 0 <= bisect.bisect_left(s, tmp1) - 1 <= a - 1 and 0 <= bisect.bisect_left(s, tmp1) <= a - 1 :
            tmp11 = s[bisect.bisect_left(s, tmp1) - 1]
            tmp12 = s[bisect.bisect_left(s, tmp1)]
            ans1 = min(abs(x[i] - tmp1) + abs(tmp1 - tmp11), abs(x[i] - tmp1) + abs(tmp1 - tmp12))
        elif 0 <= bisect.bisect_left(s, tmp1) - 1 <= a - 1:
            tmp11 = s[bisect.bisect_left(s, tmp1) - 1]
            ans1 = abs(x[i] - tmp1) + abs(tmp1 - tmp11)
        elif 0 <= bisect.bisect_left(s, tmp1) <= a - 1:
            tmp12 = s[bisect.bisect_left(s, tmp1)]
            ans1 = abs(x[i] - tmp1) + abs(tmp1 - tmp12)

        
        anss =  ans1
    
    elif 0 <= bisect.bisect_left(t, x[i]) <= b - 1 :
        tmp2 = t[bisect.bisect_left(t, x[i])]
        #tmp2
        if 0 <= bisect.bisect_left(s, tmp2) - 1 <= a - 1 and 0 <= bisect.bisect_left(s, tmp2) <= a - 1 :
            tmp21 = s[bisect.bisect_left(s, tmp2) - 1]
            tmp22 = s[bisect.bisect_left(s, tmp2)]
            ans2 = min(abs(x[i] - tmp2) + abs(tmp2 - tmp21), abs(x[i] - tmp2) + abs(tmp2 - tmp22))
        elif 0 <= bisect.bisect_left(s, tmp2) - 1 <= a - 1:
            tmp21 = s[bisect.bisect_left(s, tmp2) - 1]
            ans2 = abs(x[i] - tmp2) + abs(tmp2 - tmp21)
        elif 0 <= bisect.bisect_left(s, tmp2) <= a - 1:
            tmp22 = t[bisect.bisect_left(s, tmp2)]
            ans2 = abs(x[i] - tmp2) + abs(tmp2 - tmp22)
        anss = ans2
    
    print(min(ans, anss))

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from itertools import zip_longest
from operator import itemgetter
readline = sys.stdin.readline
a,b,q = map(int, input().split(' '))
S = [int(readline()) for _ in range(a)]
T = [int(readline()) for _ in range(b)]
Q = [int(readline()) for _ in range(q)]
st = list(zip_longest([],S,fillvalue = 1))+list(zip_longest([],T,fillvalue = 2))
st.sort(key=itemgetter(1))
st_plc = [x[1] for x in st]
for i,x in enumerate(Q):
    nb = bisect.bisect(st_plc, x)
    if nb == 0:
        print(max(S[0],T[0])-x)
    elif nb == a+b:
        print(x-min(S[-1],T[-1]))
    else:
        if st[nb-1][0] == 1:
            nb2 = bisect.bisect(T,st_plc[nb-1])
            if nb2 == 0:
                ans1 = (x-st_plc[nb-1])*2 + (T[0]-x)
            elif nb2 == b:
                ans1 = (x-st_plc[nb-1])*2 + (x-T[-1])
            else:
                ans1 = x-st_plc[nb-1] + min(T[nb2]-st_plc[nb-1],st_plc[nb-1]-T[nb2-1])
        elif st[nb-1][0] == 2:
            nb2 = bisect.bisect(S,st_plc[nb-1])
            if nb2 == 0:
                ans1 = (x-st_plc[nb-1])*2 + (S[0]-x)
            elif nb2 == a:
                ans1 = (x-st_plc[nb-1])*2 + (x-S[-1])
            else:
                ans1 = x-st_plc[nb-1] + min(S[nb2]-st_plc[nb-1],st_plc[nb-1]-S[nb2-1])
        if st[nb][0] == 1:
            nb2 = bisect.bisect(T,st_plc[nb])
            if nb2 == 0:
                ans2 = (st_plc[nb]-x)*2 + (T[0]-x)
            elif nb2 == b:
                ans2 = (st_plc[nb]-x)*2 + (x-T[-1])
            else:
                ans2 = st_plc[nb]-x + min(T[nb2]-st_plc[nb],st_plc[nb]-T[nb2-1])
        elif st[nb][0] == 2:
            nb2 = bisect.bisect(S,st_plc[nb])
            if nb2 == 0:
                ans2 = (st_plc[nb]-x)*2 + (S[0]-x)
            elif nb2 == a:
                ans2 = (st_plc[nb]-x)*2 + (x-S[-1])
            else:
                ans2 = st_plc[nb]-x + min(S[nb2]-st_plc[nb],st_plc[nb]-S[nb2-1])
        print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from itertools import zip_longest
from operator import itemgetter
readline = sys.stdin.readline
a,b,q = map(int, input().split(' '))
S = [int(readline()) for _ in range(a)]
T = [int(readline()) for _ in range(b)]
Q = [int(readline()) for _ in range(q)]
st = list(zip_longest([],S,fillvalue = 1))+list(zip_longest([],T,fillvalue = 2))
st.sort(key=itemgetter(1))
st_plc = [x[1] for x in st]
for i,x in enumerate(Q):
    nb = bisect.bisect(st_plc, x)
    if nb == 0:
        print(max(S[0],T[0]))
    elif nb == a+b:
        print(x-min(S[-1],T[-1]))
    else:
        if st[nb-1][0] == 1:
            nb2 = bisect.bisect(T,st_plc[nb-1])
            if nb2 == 0:
                ans1 = (x-st_plc[nb-1])*2 + (T[0]-x)
            elif nb2 == b:
                ans1 = (x-st_plc[nb-1])*2 + (x-T[-1])
            else:
                ans1 = x-st_plc[nb-1] + min(T[nb2]-st_plc[nb-1],st_plc[nb-1]-T[nb2-1])
        elif st[nb-1][0] == 2:
            nb2 = bisect.bisect(S,st_plc[nb-1])
            if nb2 == 0:
                ans1 = (x-st_plc[nb-1])*2 + (S[0]-x)
            elif nb2 == a:
                ans1 = (x-st_plc[nb-1])*2 + (x-S[-1])
            else:
                ans1 = x-st_plc[nb-1] + min(S[nb2]-st_plc[nb-1],st_plc[nb-1]-S[nb2-1])
        if st[nb][0] == 1:
            nb2 = bisect.bisect(T,st_plc[nb])
            if nb2 == 0:
                ans2 = (st_plc[nb]-x)*2 + (T[0]-x)
            elif nb2 == b:
                ans2 = (st_plc[nb]-x)*2 + (x-T[-1])
            else:
                ans2 = st_plc[nb]-x + min(T[nb2]-st_plc[nb],st_plc[nb]-T[nb2-1])
        elif st[nb][0] == 2:
            nb2 = bisect.bisect(S,st_plc[nb])
            if nb2 == 0:
                ans2 = (st_plc[nb]-x)*2 + (S[0]-x)
            elif nb2 == a:
                ans2 = (st_plc[nb]-x)*2 + (x-S[-1])
            else:
                ans2 = st_plc[nb]-x + min(S[nb2]-st_plc[nb],st_plc[nb]-S[nb2-1])
        print(min(ans1,ans2))

Submission status: Wrong Answer

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

import sys
from bisect import bisect_left

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M, Q = MAP()
A = [0] * N
for i in range(N):
    A[i] = INT()
B = [0] * M
for i in range(M):
    B[i] = INT()

A.sort()
B.sort()
A = [-INF] + A + [INF]
B = [-INF] + B + [INF]

def calc(A, B):
    dist = 0
    # 先に行く方
    ra = bisect_left(A, q)
    la = ra - 1
    if q-A[la] <= A[ra]-q:
        dist += q-A[la]
        nxt = A[la]
    else:
        dist += A[ra]-q
        nxt = A[ra]
    # 後に行く方
    rb = bisect_left(B, nxt)
    lb = rb - 1
    if nxt-B[lb] <= B[rb]-nxt:
        dist += nxt-B[lb]
    else:
        dist += B[rb]-nxt
    return dist

for i in range(Q):
    q = INT()
    # 神社、寺の順で行く
    dist1 = calc(A, B)
    # 寺、神社の順で行く
    dist2 = calc(B, A)
    print(min(dist1, dist2))

Submission status: Wrong Answer

Solution code:
import bisect
A,B,Q=map(int,input().split())
INF=10**18
S=[-INF]+[int(input()) for i in range(A)]+[INF]
T=[-INF]+[int(input()) for i in range(B)]+[INF]
for q in range(Q):
    x=int(input())
    i=bisect.bisect_right(S,x)
    j=bisect.bisect_right(T,x)
    d=INF
    for s in [S[i-1],S[i]]:
        for t in [T[j-1],T[j]]:
            d1=abs(s-x)+abs(s-t)
            d2=abs(t-x)+abs(s-t)
            d=min(d1,d2)
    print(d)

Submission status: Wrong Answer

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

print(S)
print(T)

for q in range(Q):
    x=int(input())
    i=bisect.bisect_right(S,x)
    j=bisect.bisect_right(T,x)
    d=INF
    for s in [S[i-1],S[i]]:
        for t in [T[j-1],T[j]]:
            d1=abs(s-x)+abs(s-t)
            d2=abs(t-x)+abs(s-t)
            d=min(d1,d2)
    print(d)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
A,B,Q = map(int,input().split())
jinjya = [-float('inf')]+[int(input()) for _ in range(A)]+[float('inf')]
#範囲を絞るために両サイドに無限大を挿入。最小値には影響しない
tera =[-float('inf')]+[int(input()) for _ in range(B)]+[float('inf')]

for i in range(Q):
  x=int(input())
  
  L=0
  R=A+2
  while R-L>1:
    P=(R+L)//2
    if jinjya[P]<x:
      L=P
    else:
      R=P
  J_L=L
  
  L=0
  R=B+2
  while R-L>1:
    P=(R+L)//2
    if tera[P]<x:
      L=P
    else:
      R=P
  T_L=L
  a=jinjya[J_L]
  b=jinjya[J_L+1]
  c=tera[T_L]
  d=tera[T_L+1]

  answer=min(abs(x-a)+abs(a-c),abs(x-c)+abs(c-a),abs(x-b)+abs(b-c),abs(x-c)+abs(c-b),abs(x-a)+abs(a-d),abs(x-d)+abs(d-a),abs(x-b)+abs(b-d),abs(x-d)+abs(d-b))
  print(answer)