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: Accepted

Solution code:
a,b,q=map(int,input().split())
from bisect import bisect_left
s_list=[]
for i in range(a):
    s_list.append(int(input()))
t_list=[]
for i in range(b):
    t_list.append(int(input()))
for i in range(q):
    x=int(input())
    s_i=bisect_left(s_list,x)
    t_i=bisect_left(t_list,x)
    sL=[]
    if s_i==0:
        sL.append(s_list[0])
    elif s_i==a:
        sL.append(s_list[a-1])
    else:
        sL.append(s_list[s_i-1])
        sL.append(s_list[s_i])
    tL=[]
    if t_i==0:
        tL.append(t_list[0])
    elif t_i==b:
        tL.append(t_list[b-1])
    else:
        tL.append(t_list[t_i-1])
        tL.append(t_list[t_i])
    Min=10**16
    for i in sL:
        for j in tL:
            Min=min(Min,abs(x-i)+abs(j-i))
            Min=min(Min,abs(x-j)+abs(j-i))
    print(Min)

Submission status: Accepted

Solution code:
from bisect 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")]
xn = [int(input()) for _ in range(q)]

for x in xn:
    min_d = 0

    sx = bisect(s, x)
    tx = bisect(t, x)

    min_d = min(x - min(s[sx-1], t[tx-1]),
                max(s[sx], t[tx]) - x,
                2 * (x - s[sx-1]) + t[tx] - x,
                2 * (x - t[tx-1]) + s[sx] - x,
                2 * (t[tx] - x) + x - s[sx-1],
                2 * (s[sx] - x) + x - t[tx-1])

    print(min_d)

Submission status: Accepted

Solution code:
from bisect import bisect, bisect_left
inf = float('inf')

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

def solve(x):
    si = bisect(S,x)
    sl,sr = S[si-1],S[si]
    ti = bisect(T,x)
    tl,tr = T[ti-1],T[ti]
    ans = inf
    for s in [sl,sr]:
        for t in [tl,tr]:
            res0 = abs(s-x) + abs(s-t)
            res1 = abs(t-x) + abs(s-t)
            ans = min(ans,res0,res1)
    return ans

for x in X:
    ans = solve(x)
    print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from bisect import bisect_left

def find_left_right(lis: list, pos: int):
    left_idx = bisect_left(lis, pos) - 1
    left = lis[left_idx]
    right = lis[left_idx+1]
    return left, right

def find_min(sh_l, sh_r, tm_l, tm_r, x):
    ret = 10**18
    ret = min(ret, max(x-sh_l, x-tm_l))
    ret = min(ret, (tm_r - sh_l + min(x-sh_l, tm_r-x)))
    ret = min(ret, (sh_r - tm_l + min(x-tm_l, sh_r-x)))
    ret = min(ret, max(sh_r-x, tm_r-x))

    return ret

a,b,q = li()
INF = 10**18
s = [-INF] + [ni() for _ in range(a)] + [INF]
t = [-INF] + [ni() for _ in range(b)] + [INF]
x = [ni() for _ in range(q)]

for xi in x:
    shrine_left, shrine_right = find_left_right(s, xi)
    temple_left, temple_right = find_left_right(t, xi)
    print(find_min(shrine_left, shrine_right, temple_left, temple_right, xi))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left
A, B, Q = map(int, input().split())
minf, inf = -(10**18), 10**18
jinja = [minf] + list(map(int, (sys.stdin.readline() for _ in [0]*A))) + [inf]
tera = [minf] + list(map(int, (sys.stdin.readline() for _ in [0]*B))) + [inf]
queries = list(map(int, sys.stdin))
 
for q in queries:
    i = bisect_left(jinja, q)
    j = bisect_left(tera, q)
    left_jinja, right_jinja = q-jinja[i-1], jinja[i]-q
    left_tera, right_tera = q-tera[j-1], tera[j]-q
 
    res = min(
        max(left_jinja, left_tera),
        left_jinja + right_tera + min(left_jinja, right_tera),
        right_jinja + left_tera + min(right_jinja, left_tera),
        max(right_jinja, right_tera)
    )
    print(res)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
a, b, q = list(map(int, input().split()))
s = [int(input()) for i in range(a)]
t = [int(input()) for i in range(b)]
for i in range(q):
  x = int(input())
  ss = bisect_left(s, x)
  tt = bisect_left(t, x)
  d1, d2, d3, d4 = 1e12, 1e12, 1e12, 1e12
  if ss-1>=0 and tt-1>=0:
    d1 = max((x-s[ss-1]), (x-t[tt-1]))
  if ss-1>=0 and tt<b:
    d2 = (x-s[ss-1])+(t[tt]-x)+min((x-s[ss-1]), (t[tt]-x))
  if ss<a and tt-1>=0:
    d3 = (s[ss]-x)+(x-t[tt-1])+min((s[ss]-x), (x-t[tt-1]))
  if ss<a and tt<b:
    d4 = max((s[ss]-x), (t[tt]-x))
  ans = min(d1, d2, d3, d4)
  print(ans)

Submission status: Accepted

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

INF = 10 ** 18
S = []
for i in range(A):
    S.append(int(input()))

S = [-INF] + S + [INF]

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

T = [-INF] + T + [INF]


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

Submission status: Accepted

Solution code:
import bisect

A, B, Q = [int(e) for e in input().split()]
ss = [int(input()) for _ in range(A)]
tt = [int(input()) for _ in range(B)]
xx = [int(input()) for _ in range(Q)]
INF = 10 ** 18
for x in xx:
    idx_s_right = min(bisect.bisect_left(ss, x), A-1)
    idx_s_left = max(0, idx_s_right - 1)
    stmps = [ss[idx_s_right], ss[idx_s_left]]

    ttmps = [] 
    idx_t_right = min(bisect.bisect_left(tt, x), B-1)
    idx_t_left = max(0, idx_t_right - 1)
    ttmps = [tt[idx_t_right], tt[idx_t_left]]

    mem = INF
    for s in stmps:
        for t in ttmps:
            d_s = abs(s - x) + abs(t - s)
            d_t = abs(t - x) + abs(s - t)
            mem = min(mem, d_s, d_t)
    print(mem)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


class BisectWrapper:
    try:
        from typing import List
    except:
        List = list
    from bisect import bisect, bisect_left, bisect_right

    def __init__(self):
        pass

    # aにxが存在するか
    @staticmethod
    def exist(a: List, x: int):
        i = bisect_left(a, x)
        if i != len(a) and a[i] == x:
            return True
        return False

    # xのindex(なければ-1)
    @staticmethod
    def index(a: List, x: int):
        i = bisect_left(a, x)
        if i != len(a) and a[i] == x:
            return i
        return -1

    # y < xのようなyの中でもっとも右のindex
    @staticmethod
    def index_lt(a: List, x: int):
        i = bisect_left(a, x)
        if i:
            return i - 1
        return -1

    # y < xのようなyの個数
    @staticmethod
    def num_lt(a: List, x: int):
        return bisect_left(a, x)

    # y <= xのようなyの中でもっとも右のindex
    @staticmethod
    def index_lte(a: List, x: int):
        i = bisect_right(a, x)
        if i:
            return i - 1
        return -1

    # y < xのようなyの個数
    @staticmethod
    def num_lte(a: List, x: int):
        return bisect_right(a, x)

    # y > xのようなyの中でもっとも左のindex
    @staticmethod
    def index_gt(a: List, x: int):
        i = bisect_right(a, x)
        if i != len(a):
            return i
        return -1

    # y > xのようなyの個数
    @staticmethod
    def num_gt(a: List, x: int):
        return len(a) - bisect_right(a, x)

    # y >= xのようなyの中でもっとも左のindex
    @staticmethod
    def index_gte(a: List, x: int):
        i = bisect_left(a, x)
        if i != len(a):
            return i
        return -1

    # y >= xのようなyの個数
    @staticmethod
    def num_gte(a: List, x: int):
        return len(a) - bisect_left(a, x)


def near(A, x):
    l = BisectWrapper.index_lte(A, x)
    r = l + 1
    if l == -1:
        return abs(x - A[r])
    if r >= len(A):
        return abs(x - A[l])
    return min(abs(x - A[r]), abs(x - A[l]))


def main():
    A, B, Q = map(int, input().split())
    S = [int(input()) for _ in range(A)]
    T = [int(input()) for _ in range(B)]

    for _ in range(Q):
        x = int(input())

        ans = INF
        s_l = BisectWrapper.index_lte(S, x)
        if s_l != -1:
            s = S[s_l]
            ans = min(ans, abs(x - s) + near(T, s))

        s_r = s_l + 1
        if s_r < len(S):
            s = S[s_r]
            ans = min(ans, abs(x - s) + near(T, s))

        t_l = BisectWrapper.index_lte(T, x)
        if t_l != -1:
            t = T[t_l]
            ans = min(ans, abs(x - t) + near(S, t))

        t_r = t_l + 1
        if t_r < len(T):
            t = T[t_r]
            ans = min(ans, abs(x - t) + near(S, t))

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
A,B,Q=map(int,input().split())
S=[int(input()) for i in range(A)]
T=[int(input()) for j in range(B)]
S.sort()
T.sort()
def make_lr(L,idx,x):
    if idx==0:
        return float('inf'),L[idx]-x
    if idx==len(L):
        return x-L[idx-1],float('inf')
    return x-L[idx-1],L[idx]-x
import bisect
for i in range(Q):
    x=int(input())
    Sidx=bisect.bisect_left(S,x)
    Tidx=bisect.bisect_left(T,x)
    sl,sr=make_lr(S,Sidx,x)
    tl,tr=make_lr(T,Tidx,x)
    
    print(min(sl+tr+min(sl,tr),sr+tl+min(sr,tl),min(max(sl,tl),max(sr,tr))))

Submission status: Accepted

Solution code:
from itertools import product
from bisect import bisect_left, bisect_right


def main():
    A, B, Q = map(int, input().split())
    ss = [int(input()) for _ in range(A)]
    ts = [int(input()) for _ in range(B)]
    xs = [int(input()) for _ in range(Q)]

    # gen = TLE(A, B, Q, ss, ts, xs)
    # gen = f(A, B, Q, ss, ts, xs)
    gen = editorial(A, B, Q, ss, ts, xs)
    print(*gen, sep="\n")


def TLE(A, B, Q, ss, ts, xs):
    for x in xs:
        ans = float("inf")
        for s in ss:
            for t in ts:
                if s <= x <= t or t <= x <= s:
                    ds, dt = abs(x-s), abs(x-t)
                    tmp = min(ds, dt) + abs(s-t)
                elif x <= s <= t or x <= t <= s:
                    tmp = max(s, t)-x
                elif x >= s >= t or x >= t >= s:
                    tmp = x-min(s, t)
                ans = min(ans, tmp)

        yield ans


def f_ans(s, t, x):
    if s <= x <= t or t <= x <= s:
        ds, dt = abs(x-s), abs(x-t)
        tmp = min(ds, dt) + abs(s-t)
    elif x <= s <= t or x <= t <= s:
        tmp = max(s, t)-x
    elif x >= s >= t or x >= t >= s:
        tmp = x-min(s, t)
    return tmp


def f(A, B, Q, ss, ts, xs):
    for x in xs:
        t_left = bisect_left(ts, x)
        t_right = bisect_right(ts, x)
        s_left = bisect_left(ss, x)
        s_right = bisect_right(ss, x)

        t_idx = [t_right + a for a in [-1, 0, 1]]
        t_idx += [t_left + a for a in [-1, 0, 1]]
        s_idx = [s_right + a for a in [-1, 0, 1]]
        s_idx += [s_left + a for a in [-1, 0, 1]]

        ans = float("inf")
        for si, ti in product(set(s_idx), set(t_idx)):
            if 0 <= si < A and 0 <= ti < B:
                tmp = f_ans(ss[si], ts[ti], x)
                ans = min(ans, tmp)
        yield ans


def editorial(A, B, Q, ss, ts, xs):
    INF = float("inf")
    # 番兵
    ss = [-INF] + ss + [INF]
    ts = [-INF] + ts + [INF]
    for x in xs:
        # -inf の右 [1]
        # +inf の左 [-1]
        b, d = bisect_right(ss, x), bisect_right(ts, x)
        ans = INF
        # 番兵のおかげでindex を気にしなくて良い
        for s in [ss[b - 1], ss[b]]:
            for t in [ts[d - 1], ts[d]]:
                # s--t--x, t--s--x
                # s--x--t, t--x--s
                # x--t--s, x--s--t
                d1 = abs(s - x) + abs(t - s)
                d2 = abs(t - x) + abs(s - t)
                ans = min(ans, d1, d2)

        yield ans


if __name__ == "__main__":
    main()

Submission status: Accepted

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()))
s.append(10**11)
t.append(10**11)

for i in range(q):
    x=int(input())
    ss=bisect.bisect(s,x)
    tt=bisect.bisect(t,x)
    ans=[]
    for i in [s[ss-1],s[ss]]:
        for j in [t[tt-1],t[tt]]:
            ans.append(abs(x-i)+abs(i-j))
            ans.append(abs(x-j)+abs(i-j))
    print(min(ans))

Submission status: Accepted

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()))
s.append(10**11)
t.append(10**11)

def bis(x,q):
    l=0
    r=len(q)-1
    while r-l>1:
        mid=(r+l)//2
        if q[mid]>=x:
            r=mid
        else:
            l=mid
    return q[l],q[r]

for i in range(q):
    x=int(input())
    ss=bis(x,s)
    tt=bis(x,t)
    ans=[]
    for i in ss:
        for j in tt:
            ans.append(abs(x-i)+abs(i-j))
            ans.append(abs(x-j)+abs(i-j))
    print(min(ans))

Submission status: Accepted

Solution code:
import bisect

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

t = [0] * B
for i in range(B):
    t[i] = int(input())


def find_index(arr, xi):
    t = bisect.bisect_left(arr, xi)
    if t == 0:
        return [-float('inf'), arr[0]]
    elif t == len(arr):
        return [arr[-1], float('inf')]
    else:
        return [arr[t-1], arr[t]]


def func1(a, b, x):
    return min(x-a, b-x)


def calc(xi):
    global s, t
    if xi < s[0] and xi < t[0]:
        return max(s[0] - xi, t[0] - xi)

    if xi > s[-1] and xi > t[-1]:
        return max(xi - s[-1], xi - t[-1])

    s1, s2 = find_index(s, xi)
    t1, t2 = find_index(t, xi)

    if t1 < s1 and s2 < t2:
        return func1(t1, t2, xi)

    elif s1 < t1 and t2 < s2:
        return func1(s1, s2, xi)

    elif s1 < t1 and s2 < t2:
        a1 = s2 - xi + s2 - t1
        a2 = xi - t1 + s2 - t1
        return min(a1, a2, func1(s1, t2, xi))

    else:
        a1 = t2 - xi + t2 - s1
        a2 = xi - s1 + t2 - s1
        return min(a1, a2, func1(t1, s2, xi))


for i in range(Q):
    xi = int(input())
    print(calc(xi))

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.readline
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()))
def f(list,n):
  if n<list[0]:
    return [-float("inf"),list[0]]
  elif list[-1]<n:
    return [list[-1],float("inf")]
  else:
    i=bisect.bisect_left(list,n)
    return [list[i-1],list[i]]
def g(SS,TT,x):
  a,b,c,d=x-SS[0],SS[1]-x,x-TT[0],TT[1]-x
  dis1=max(a,c)
  dis2=min(2*a+d,2*d+a)
  dis3=max(b,d)
  dis4=min(2*b+c,2*c+b)
  return min([dis1,dis2,dis3,dis4])
for i in range(q):
  x=int(input())
  print(g(f(S,x),f(T,x),x))

Submission status: Accepted

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()))
def f(list,n):
  if n<list[0]:
    return [-float("inf"),list[0]]
  elif list[-1]<n:
    return [list[-1],float("inf")]
  else:
    i=bisect.bisect_left(list,n)
    return [list[i-1],list[i]]
def g(SS,TT,x):
  a,b,c,d=x-SS[0],SS[1]-x,x-TT[0],TT[1]-x
  dis1=max(a,c)
  dis2=min(2*a+d,2*d+a)
  dis3=max(b,d)
  dis4=min(2*b+c,2*c+b)
  return min([dis1,dis2,dis3,dis4])
for i in range(q):
  x=int(input())
  print(g(f(S,x),f(T,x),x))

Submission status: Accepted

Solution code:
import bisect


def nearest_pair(lst, x):
    left = None
    right = None
    idx = bisect.bisect_left(lst, x)
    if idx != 0:
        left = lst[idx - 1]
    if idx != len(lst):
        right = lst[idx]
    return left, right


def distance(l, r, x):
    if l is None:
        return abs(r - x)
    elif r is None:
        return abs(l - x)
    else:
        return min(abs(r - x), abs(l - x))


A, B, Q = map(int, input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
Q = [int(input()) for _ in range(Q)]

for x in Q:
    s_l, s_r = nearest_pair(S, x)
    t_l, t_r = nearest_pair(T, x)

    result1 = float('inf')
    if s_l is not None:
        result1 = abs(x - s_l)
        l, r = nearest_pair(T, s_l)
        result1 += distance(l, r, s_l)

    result2 = float('inf')
    if s_r is not None:
        result2 = abs(x - s_r)
        l, r = nearest_pair(T, s_r)
        result2 += distance(l, r, s_r)

    result3 = float('inf')
    if t_l is not None:
        result3 = abs(x - t_l)
        l, r = nearest_pair(S, t_l)
        result3 += distance(l, r, t_l)

    result4 = float('inf')
    if t_r is not None:
        result4 = abs(x - t_r)
        l, r = nearest_pair(S, t_r)
        result4 += distance(l, r, t_r)

    print(min(result1, result2, result3, result4))

Submission status: Accepted

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

for e in x:
    b, d = bisect.bisect_right(s,e), bisect.bisect_right(t,e)
    a, c = b-1, d-1
    ans = INF
    for S in [s[a],s[b]]:
        for T in [t[c],t[d]]:
            d1, d2 = abs(S-e) + abs(T-S), abs(T-e) + abs(S-T)
            ans = min(ans, d1, d2)
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

A,B,Q = inpl()
s = [int(input()) for i in range(A)]
t = [int(input()) for i in range(B)]
ss = [-INF] + s + [INF]
tt = [-INF] + t + [INF]

for _ in range(Q):
    x = int(input())
    si = bisect.bisect_left(ss,x)
    ti = bisect.bisect_left(tt,x)
    sl,sr = x-ss[si-1] , ss[si]-x
    tl,tr = x-tt[ti-1] , tt[ti]-x
    ans = INF
    ans = min(ans,max(sr,tr))
    ans = min(ans,max(sl,tl))
    ans = min(ans,sl*2 + tr)
    ans = min(ans,tl*2 + sr)
    ans = min(ans,sr*2 + tl)
    ans = min(ans,tr*2 + sl)
    print(ans)

Submission status: Accepted

Solution code:
import bisect
INF = 10 ** 18

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

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())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)

Submission status: Accepted

Solution code:
import bisect

A, B, Q = map(int, input().split())
INF = 10**18
s = [-INF] + [int(input()) for y in range(A)] + [INF]
t = [-INF] + [int(input()) for z in range(B)] + [INF]


for i in range(Q):
    x = int(input())
    a = bisect.bisect_right(s, x)
    b = bisect.bisect_right(t, x)
    cost = INF
    for j in [s[a-1], s[a]]:
        for k in [t[b-1], t[b]]:
            d1, d2 = abs(j-x)+abs(j-k), abs(k-x)+abs(j-k)
            cost = min(cost, d1, d2)
    print(cost)

Submission status: Accepted

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


import bisect

mas = max(s)
mis = min(s)
mat = max(t)
mit = min(t)

for i in range(Q):
    ans = 10**20

    if mis <= x[i]:
        s_index = bisect.bisect_left(s,x[i])
        s_index -= 1
        if mat >= s[s_index]:
            t_index = bisect.bisect_left(t,s[s_index])
            ans = min(ans, abs(x[i] - s[s_index]) + abs(t[t_index] - s[s_index]))

    if mit <= x[i]:
        t_index = bisect.bisect_left(t,x[i])
        t_index -= 1
        if mas >= t[t_index]:
            s_index = bisect.bisect_left(s,t[t_index])
            ans = min(ans, abs(x[i] - t[t_index]) + abs(t[t_index] - s[s_index]))

    if mas >= x[i]:
        s_index = bisect.bisect_left(s,x[i])
        if mit <= s[s_index]:
            t_index = bisect.bisect_left(t,s[s_index])
            t_index -= 1
            ans = min(ans, abs(x[i] - s[s_index]) + abs(t[t_index] - s[s_index]))

    if mat >= x[i]:
        t_index = bisect.bisect_left(t,x[i])
        if mis <= t[t_index]:
            s_index = bisect.bisect_left(s,t[t_index])
            s_index -= 1
            ans = min(ans, abs(x[i] - t[t_index]) + abs(t[t_index] - s[s_index]))

    if mas >= x[i] and mat >= x[i]:
        s_index = bisect.bisect_left(s,x[i])
        t_index = bisect.bisect_left(t,x[i])
        ans = min(ans,abs(x[i] - max(s[s_index],t[t_index])))

    if mis <= x[i] and mit <= x[i]:
        s_index = bisect.bisect_left(s,x[i])
        s_index -= 1
        t_index = bisect.bisect_left(t,x[i])
        t_index -= 1
        ans = min(ans,abs(x[i] - min(s[s_index],t[t_index])))
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from bisect import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(A: int, B: int, Q: int, s: "List[int]", t: "List[int]", x: "List[int]"):
    rs = []
    for xx in x:
        si = bisect(s, xx)
        ti = bisect(t, xx)

        ret = float('inf')
        for ss, tt in product([s[max(0, si - 1)], s[min(si, A - 1)]], [t[max(0, ti - 1)], t[min(ti, B - 1)]]):
            ret = min(ret, abs(ss - xx) + abs(tt - ss))
            ret = min(ret, abs(tt - xx) + abs(tt - ss))
        rs.append(ret)
    return '\n'.join([str(r) for r in rs])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    s = [ int(next(tokens)) for _ in range(A) ]  # type: "List[int]"
    t = [ int(next(tokens)) for _ in range(B) ]  # type: "List[int]"
    x = [ int(next(tokens)) for _ in range(Q) ]  # type: "List[int]"
    result = solve(A, B, Q, s, t, x)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def binary_search(x, l, lo, hi):
    med = (lo + hi) // 2
    if hi - lo <= 1:
        if x < l[0]:
            return INF, abs(x-l[med])
        elif x > l[-1]:
            return abs(x-l[med]), INF
        else:
            return abs(x-l[med]), abs(x-l[med+1])

    if x > l[med]:
        return binary_search(x, l, med, hi)
    elif x < l[med]:
        return binary_search(x, l, lo, med)
    else:
        return 0, 0


for i in x:
    sl, sr = binary_search(i, s, 0, len(s))
    tl, tr = binary_search(i, t, 0, len(t))

    if tl >= sl and tr >= sr:
        print(min(tl, tr))
    elif sl >= tl and sr >= tr:
        print(min(sl, sr))
    elif tl >= sl and sr >= tr:
        sl1 = min(tl, 2*sl+tr)
        tr1 = min(sr, 2*tr+sl)
        print(min(sl1, tr1))
    else:
        tl1 = min(sl, 2*tl+sr)
        sr1 = min(tr, 2*sr+tl)
        print(min(tl1, sr1))

Submission status: Accepted

Solution code:
# 二部探索問題

# from bisect import bisect_right as binarysearch
A, B, Q = map(int,input().split())

"""
自分で作ったやつは遅い
"""
def binarysearch(ls,x):
    n = len(ls)
    left = 0
    right = n
    pos = (right+left)//2
    while True:
        if ls[pos] < x < ls[pos+1]:
            index = pos
            break    
        elif x < ls[pos]:
            right = pos
        elif ls[pos+1] < x:
            left = pos
        pos = (right+left)//2
    return index




ss = [-10**10]+[int(input()) for _ in range(A)]+[2*10**10]
ts = [-10**10]+[int(input()) for _ in range(B)]+[2*10**10]
xs = [int(input()) for _ in range(Q)]
for x in xs:
    sind = binarysearch(ss,x)
    tind = binarysearch(ts,x)
    
    s0,s1,t0,t1 = ss[sind],ss[sind+1],ts[tind],ts[tind+1]
    # d1,d2,d3,d4 = 10**10,10**10,10**10,10**10
    # print("s",s0,x,s1)
    # print("t",t0,x,t1)
    d1 = max(x-s0,x-t0)
    d2 = min((t1-x)*2+(x-s0),(x-s0)*2+(t1-x))
    d3 = min((s1-x)*2+(x-t0),(x-t0)*2+(s1-x))
    d4 = max(s1-x, t1-x)
    print(min(d1,d2,d3,d4))

Submission status: Accepted

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

ss = [-10**10]+[int(input()) for _ in range(A)]+[2*10**10]
ts = [-10**10]+[int(input()) for _ in range(B)]+[2*10**10]
xs = [int(input()) for _ in range(Q)]
for x in xs:
    sind = binarysearch(ss,x)-1
    tind = binarysearch(ts,x)-1
    
    s0,s1,t0,t1 = ss[sind],ss[sind+1],ts[tind],ts[tind+1]
    d1,d2,d3,d4 = 10**10,10**10,10**10,10**10

    d1 = max(x-s0,x-t0)
    d2 = min((t1-x)*2+(x-s0),(x-s0)*2+(t1-x))
    d3 = min((s1-x)*2+(x-t0),(x-t0)*2+(s1-x))
    d4 = max(s1-x, t1-x)
    print(min(d1,d2,d3,d4))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
import itertools
import sys


def most_simRL(ds, x):
    index = bisect.bisect_left(ds, x)
    if index == 0:
        return [ds[0]]
    elif index == len(ds):
        return [ds[-1]]
    return ds[index-1:index+1]

if __name__ == '__main__':
    A, B, Q = map(int, input().split())


    s_list = [-sys.maxsize] + [int(input()) for i in range(A)] + [sys.maxsize]
    t_list = [-sys.maxsize] + [int(input()) for i in range(B)] + [sys.maxsize]
    x_list = [int(input()) for i in range(Q)]


    for xi in x_list:
        s_RL = most_simRL(s_list, xi)
        t_RL = most_simRL(t_list, xi)

        answer = sys.maxsize

        for a, b in itertools.product(s_RL, t_RL):
            answer = min(answer, min(abs(xi-a), abs(xi-b)) + abs(a-b))

        print(answer)

Submission status: Accepted

Solution code:
import bisect
import itertools

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


def most_simRL(ds, x):
    index = bisect.bisect(ds, x)
    return ds[index-1:index+1]


for x in X:
    s_ind = bisect.bisect(s, x)
    t_ind = bisect.bisect(t, x)
    ans = inf
    for a, b in itertools.product((s[s_ind-1], s[s_ind]), (t[t_ind-1], t[t_ind])):
        ans = min(ans, min(abs(a-x), abs(b-x)) + abs(a-b))
    print(ans)

Submission status: Accepted

Solution code:
import bisect
import itertools
import sys

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


def most_simRL(ds, x):
    index = bisect.bisect_left(ds, x)
    if index == 0:
        return [ds[0]]
    elif index == len(ds):
        return [ds[-1]]
    return ds[index-1:index+1]


for x in X:
    s_RL = most_simRL(s, x)
    t_RL = most_simRL(t, x)
    ans = sys.maxsize
    for a, b in itertools.product(s_RL, t_RL):
        ans = min(ans, min(abs(a-x), abs(b-x)) + abs(a-b))
    print(ans)