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:
import itertools
import bisect
import sys
input = sys.stdin.readline


def main():
    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:
        i_s = bisect.bisect_left(S, x)
        i_t = bisect.bisect_left(T, x)
        Cs = []
        Ct = []
        if i_s!=0:
            s_l = S[i_s - 1]
            Cs.append(s_l)
        if i_s!=len(S):
            s_r = S[i_s]
            Cs.append(s_r)
        if i_t!=0:
            t_l = T[i_t - 1]
            Ct.append(t_l)
        if i_t!=len(T):
            t_r = T[i_t]
            Ct.append(t_r)
        # print(x)
        # print(Cs)
        # print(Ct)
        ans = float('inf')
        for C in itertools.product(Cs, Ct):
            ans = min(ans, abs(x-C[0])+abs(C[0]-C[1]))
            ans = min(ans, abs(x-C[1])+abs(C[1]-C[0]))
            # print(C)
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
 
a,b,q = map(int,input().split())
inf = 10**18
S = [-inf]+[int(input()) for _ in range(a)]+[inf]
T = [-inf]+[int(input()) for _ in range(b)]+[inf]
ans = inf
for _ in range(q):
  x = int(input())
  b,d = bisect.bisect_right(S,x),bisect.bisect_right(T,x)
  ans = inf
  for s in [S[b-1],S[b]]:
    for t in [T[d-1],T[d]]:
      tmp1,tmp2 = abs(s-x)+abs(s-t) ,abs(t-x)+abs(t-s)
      ans = min(ans ,tmp1,tmp2)
  print(ans)

Submission status: Accepted

Solution code:
import bisect 

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

INF = float("inf")
#受け取りなど
A, B, Q = getlist()
S = [-INF]
for i in range(A):
	s = int(input())
	S.append(s)
S.append(INF)

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

for i in range(Q):
	x = int(input())
	a = bisect.bisect_left(S, x)
	b = bisect.bisect_left(T, x)
	print(min(max(x - S[a - 1], x - T[b - 1]), max(S[a] - x, T[b] - x), (S[a] - x) * 2 + x - T[b - 1], (T[b] - x) * 2 + x - S[a - 1], S[a] - x + (x - T[b - 1]) * 2, T[b] - x + (x - S[a - 1]) * 2))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    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)]
    from bisect import bisect
    for x in X:
        i=bisect(S,x)
        j=bisect(T,x)
        sleft=x-S[i-1]
        sright=S[i]-x
        tleft=x-T[j-1]
        tright=T[j]-x
        LL=max(sleft,tleft)
        RR=max(sright,tright)
        LR=sleft+tright+min(sleft,tright)
        RL=sright+tleft+min(sright,tleft)
        print(min(LL,RR,LR,RL))

resolve()

Submission status: Accepted

Solution code:
import bisect
import sys
input=sys.stdin.readline
a,b,q=map(int,input().split())
s=[-999999999999]+[int(input()) for i in range(a)]+[999999999999]
t=[-999999999999]+[int(input()) for i in range(b)]+[999999999999]
x=[int(input()) for i in range(q)]
for i in range(q):
  a1=s[bisect.bisect_left(s,x[i])-1]
  a2=s[bisect.bisect_left(s,x[i])]
  b1=t[bisect.bisect_left(t,x[i])-1]
  b2=t[bisect.bisect_left(t,x[i])]
  l=[]
  for j in [a1,a2]:
    for k in [b1,b2]:
      l.append(abs(j-k)+min(abs(x[i]-j),abs(x[i]-k)))
  print(min(l))

Submission status: Accepted

Solution code:
import bisect
a,b,q=map(int,input().split())
s=[-999999999999]+[int(input()) for i in range(a)]+[999999999999]
t=[-999999999999]+[int(input()) for i in range(b)]+[999999999999]
x=[int(input()) for i in range(q)]
for i in range(q):
  a1=s[bisect.bisect_left(s,x[i])-1]
  a2=s[bisect.bisect_left(s,x[i])]
  b1=t[bisect.bisect_left(t,x[i])-1]
  b2=t[bisect.bisect_left(t,x[i])]
  l=[]
  for j in [a1,a2]:
    for k in [b1,b2]:
      l.append(abs(j-k)+min(abs(x[i]-j),abs(x[i]-k)))
  print(min(l))

Submission status: Accepted

Solution code:
import bisect

a,b,q=map(int,input().split())
tem=[-10**18]+[int(input()) for _ in range(a)]+[10**18]
shr=[-10**18]+[int(input()) for _ in range(b)]+[10**18]
ans=[]

for _ in range(q):
    x=int(input())
    t=bisect.bisect_right(tem, x)
    s=bisect.bisect_right(shr, x)
    dt=[tem[t-1], tem[t]]
    ds=[shr[s-1], shr[s]]

    res=10**18
    for i in dt:
        for j in ds:
            d1=abs(x-i)+abs(i-j)
            d2=abs(x-j)+abs(i-j)
            res=min(res, d1, d2)
    ans.append(res)

print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import bisect

a, b, q = map(int, input().split())
ss = sorted([int(input()) for _ in range(a)] + [float('inf'), -float('inf')])
ts = sorted([int(input()) for _ in range(b)] + [float('inf'), -float('inf')])
xs = [int(input()) for _ in range(q)]

for x in xs:
    sindex = bisect.bisect(ss, x)
    sl = x - ss[sindex - 1]
    sr = ss[sindex] - x
    tindex = bisect.bisect(ts, x)
    tl = x - ts[tindex - 1]
    tr = ts[tindex] - x
    print(
        min([
            max(sl, tl),
            max(sr, tr),
            2 * sl + tr,
            2 * tl + sr,
            2 * sr + tl,
            2 * tr + sl,
        ]))

Submission status: Accepted

Solution code:
import bisect

a, b, q = map(int, input().split())
ss = sorted([int(input()) for _ in range(a)])
ts = sorted([int(input()) for _ in range(b)])
xs = [int(input()) for _ in range(q)]

for x in xs:
    sindex = bisect.bisect(ss, x)
    if sindex == 0:
        sl = float('inf')
        sr = ss[sindex] - x
    elif sindex == a:
        sl = x - ss[sindex - 1]
        sr = float('inf')
    else:
        sl = x - ss[sindex - 1]
        sr = ss[sindex] - x
    tindex = bisect.bisect(ts, x)
    if tindex == 0:
        tl = float('inf')
        tr = ts[tindex] - x
    elif tindex == b:
        tl = x - ts[tindex - 1]
        tr = float('inf')
    else:
        tl = x - ts[tindex - 1]
        tr = ts[tindex] - x
    print(
        min([
            max(sl, tl),
            max(sr, tr),
            2 * sl + tr,
            2 * tl + sr,
            2 * sr + tl,
            2 * tr + sl,
        ]))

Submission status: Accepted

Solution code:
import sys
import bisect
MAX_INT = int(10e12)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def distance(list, index, x):
  res = abs(x - list[index][0])
  return res

def distance2(list, index, x):
  res = abs(x - list[index])
  return res

# 二分探索 #
def nibutan(list,n):
    left = -1
    right = len(list)
    while left+1 != right:
        middle = (left+right)//2
        if list[middle][0] <= n:
            left = middle
        else:
            right = middle
    return right

A,B,Q = IL()
a = [I() for i in range(A)] # 0
b = [I() for i in range(B)] # 1
q = [I() for i in range(Q)]
ab = []

a.sort()
b.sort()

for i in a:
  ab.append([i,0])
for i in b:
  ab.append([i,1])
ab.sort()

for x in q:
  ans = MAX_INT
  ID = nibutan(ab, x)
  for i in [-1,0]:
    if 0 <= ID+i < len(ab):
      if ab[ID+i][1] == 0: # a → b
        for j in [-1,0]:
          ID2 = bisect.bisect_left(b, ab[ID+i][0])
          if 0 <= ID2+j < len(b):
            dis = distance(ab, ID+i, x)
            dis += distance2(b, ID2+j, ab[ID+i][0])
            ans = min(ans, dis)
      else: # b → a
        for j in [-1,0]:
          ID2 = bisect.bisect_left(a, ab[ID+i][0])
          if 0 <= ID2+j < len(a):
            dis = distance(ab, ID+i, x)
            dis += distance2(a, ID2+j, ab[ID+i][0])
            ans = min(ans, dis)
  print(ans)

Submission status: Accepted

Solution code:
#22:10
a,b,q = map(int,input().split())
s = []
for _ in range(a):
  s.append(int(input()))
t = []
for _ in range(b):
  t.append(int(input()))
import bisect
st = []
for i in range(a):
  tmp = bisect.bisect_left(t,s[i])
  if tmp == 0:
    st.append(abs(s[i]-t[tmp]))
  elif tmp == b:
    st.append(abs(s[i]-t[tmp-1]))
  else:
    st.append(min(abs(s[i]-t[tmp-1]),abs(s[i]-t[tmp])))
ts = []
for j in range(b):
  tmp = bisect.bisect_left(s,t[j])
  if tmp == 0:
    ts.append(abs(t[j]-s[tmp]))
  elif tmp == a:
    ts.append(abs(t[j]-s[tmp-1]))
  else:
    ts.append(min(abs(t[j]-s[tmp-1]),abs(t[j]-s[tmp])))
'''
print(s)
print(t)
print(st)
print(ts)
'''
for _ in range(q):
  x = int(input())
  can = []
  xs = bisect.bisect_left(s,x)
  xt = bisect.bisect_left(t,x)
  try:
    can.append(abs(x-s[xs-1]) + st[xs-1])
  except:
    pass
  try:
    can.append(abs(x-s[xs])   + st[xs])
  except:
    pass
  try:
    can.append(abs(x-t[xt-1]) + ts[xt-1])
  except:
    pass
  try:
    can.append(abs(x-t[xt])   + ts[xt])
  except:
    pass
  print(min(can))

Submission status: Accepted

Solution code:
import bisect
a,b,q = map(int,input().split())
s = []
ans = []
for i in range(a):
    s0 = int(input())
    s.append(s0)
t = []
for i in range(b):
    t0 = int(input())
    t.append(t0)
for i in range(q):
    x = int(input())
    m = bisect.bisect_left(s,x)
    n = bisect.bisect_left(t,x)
    ai = []
    bi = []
    ansl = []
    if m > 0 and m < a:
        ai.append(s[m])
        ai.append(s[m-1])
    elif m == 0:
        ai.append(s[m])
    else:
        ai.append(s[m-1])
    if n > 0 and n < b:
        bi.append(t[n])
        bi.append(t[n-1])
    elif n == 0:
        bi.append(t[n])
    else:
        bi.append(t[n-1])
    for j in ai:
        for k in bi:
            if (j-x)*(k-x) > 0:
                ansl.append(max(abs(j-x),abs(k-x)))
            else:
                ansl.append(abs(j-k)+abs(j-x))
                ansl.append(abs(j-k)+abs(k-x))
    ans.append(min(ansl))
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
from random import shuffle
import cProfile
sys.setrecursionlimit(200000)
# local only
# if not __debug__:
#     fin = open('text.txt', 'r')
#     sys.stdin = fin
# local only
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

# BEGIN CUT HERE
class Avltree:
    """
    AVL木

    Methods
    -------
        search(x: int) -> Union(int)
            ◯.data == x のものが存在するある場合それを出力、ない場合 None を返す
        insert(x: int) -> None
            ◯.data == x がない場合 ◯.data == x なる頂点を作る。ある場合はなにもしない（上書きしない）
        y.to_s() -> int
            頂点yのdataを返す
        y.left_s() -> Union(int, key=None)
            頂点yのleftを返す(ない場合は key)
        search_lower(x: int, key_lower) -> int
            ○.data が x より小さいものの中で最も大きいものを出力、ない場合 key_lower を返す
        search_higher(x:int , key_higher) -> int
            ○.data が x より大きいものの中で最も小さいものを出力、ない場合 key_higher を返す
    """

    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None
        self.balance = "Even"

    def search(self, key):
        node = self
        while node is not None:
            if node.key == key:
                return node  # node.key == keyの場合
            if node.key > key:
                node = node.left
            elif node.key < key:
                node = node.right
        return None

    def search_lower(self, key, key_lower):
        node = self
        if node.key is None:
            return key_lower
        ans = key_lower
        while node is not None:
            if node.key < key:
                if ans < node.key:
                    ans = node.key
                node = node.right
            elif node.key >= key:
                node = node.left
        return ans

    def search_higher(self, key, key_higher):
        node = self
        if node.key is None:
            return key_higher
        ans = key_higher
        while node is not None:
            if node.key > key:
                if ans > node.key:
                    ans = node.key
                node = node.left
            elif node.key <= key:
                node = node.right
        return ans


    def end_lower(self, end_lower_key):
        node = self
        while node.left is not None:
            node = node.left
        return node.key

    def end_higher(self, end_higher_key):
        node = self
        while node.right is not None:
            node = node.right
        return node.key


    def DoubleRightRotation(self):
        tl = self.left
        self.left = tl.right.right
        tl.right.right = self  # selfはそのノード
        tlr = tl.right
        tl.right = tlr.left
        tlr.left = tl
        if tlr.balance == "Left":
            tlr.right.balance = "Right"
            tlr.left.balance = "Even"
        elif tlr.balance == "Right":
            tlr.right.balance = "Even"
            tlr.left.balance = "Left"
        elif tlr.balance == "Even":
            tlr.right.balance = "Even"
            tlr.left.balance = "Even"
        tlr.balance = "Even"
        return tlr
    def DoubleLeftRotation(self):
        tr = self.right
        self.right = tr.left.left
        tr.left.left = self
        trl = tr.left
        tr.left = trl.right
        trl.right = tr
        if trl.balance == "Right":
            trl.left.balance = "Left"
            trl.right.balance = "Even"
        elif trl.balance == "Left":
            trl.left.balance = "Even"
            trl.right.balance = "Right"
        elif trl.balance == "Even":
            trl.left.balance = "Even"
            trl.right.balance = "Even"
        trl.balance = "Even"
        return trl
    def SingleLeftRotation(self):
        tr = self.right
        tr.balance = "Even"
        self.balance = "Even"
        self.right = tr.left
        tr.left = self
        return tr
    def SingleRightRotation(self):
        tl = self.left
        tl.balance = "Even"
        self.balance = "Even"
        self.left = tl.right
        tl.right = self
        return tl
    def replace(self, p, v):  # 親ノードpの下にある自分(self)をvに置き換える。
        if p.left == self:
            p.left = v
        else:
            p.right = v
    def insert(self, key):  # rootでのみ呼ばれる挿入
        if self.key is None:  # rootを含むrotationはしないことにする。
            self.key = key
            return self
        if key < self.key:
            if self.left is None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self, key)
        elif key > self.key:
            if self.right is None:
                self.right = Avltree(key)
            else:
                self.right.insertx(self, key)
        else:  # key == self.key:
            pass  # do not overwrite
    def insertx(self, p, key):  # replaceを呼ぶために一つ上の親を持っているinsert
        node = self
        s = []
        while True:
            if node.key > key:
                s.append((node, -1))
                if node.left is None:
                    node.left = Avltree(key)
                    node = node.left
                    break
                else:
                    node = node.left
            elif node.key < key:
                s.append((node, 1))
                if node.right is None:
                    node.right = Avltree(key)
                    node = node.right
                    break
                else:
                    node = node.right
        while len(s) != 0:
            node, direct = s.pop()
            if len(s) != 0:
                par = s[-1][0]
            else:
                par = p
            if direct == -1:
                if node.balance == "Right":
                    node.balance = "Even"
                    break
                elif node.balance == "Even":
                    node.balance = "Left"
                elif node.balance == "Left":
                    if node.left.balance == "Right":
                        node.replace(par, node.DoubleRightRotation())
                    elif node.left.balance == "Left":
                        node.replace(par, node.SingleRightRotation())
                    break
            elif direct == 1:
                if node.balance == "Left":
                    node.balance = "Even"
                    break
                elif node.balance == "Even":
                    node.balance = "Right"
                elif node.balance == "Right":
                    if node.right.balance == "Left":
                        node.replace(par, node.DoubleLeftRotation())
                    elif node.right.balance == "Right":
                        node.replace(par, node.SingleLeftRotation())
                    break

    def to_s(self):
        return self.key
    def left_s(self):
        if self.left is None:
            return None
        return (self.left).key
    def right_s(self):
        if self.right is None:
            return None
        return (self.right).key
# END CUT HERE



def main():
    rb1 = Avltree()
    a, b, q = map(int, input().split())

    rb2 = Avltree()
    for i in range(a):
        s = ii()
        rb1.insert(s)
    for i in range(b):
        t = ii()
        rb2.insert(t)
    # rb1.output()
    # rb2.output()
    for i in range(q):
        x = ii()
        s1 = rb1.search_lower(x, -10**18)
        s2 = rb1.search_higher(x, 10**18)
        t1 = rb2.search_lower(x, -10**18)
        t2 = rb2.search_higher(x, 10**18)
        # print(s1, s2, t1, t2)
        res = 10**18
        for S in [s1, s2]:
            for T in [t1, t2]:
                d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
                res = min(res, d1, d2)
        print(res)




if __name__ == '__main__':
    # cProfile.run('main()')
    main()

Submission status: Accepted

Solution code:
import bisect

def search_idx_options(input_list, input_list_len, target_val):
  idx_left = bisect.bisect_left(input_list, target_val)
  if idx_left == -1: idxs = [0]
  elif  idx_left == input_list_len: idxs = [input_list_len-1]
  else: idxs = [idx_left-1, idx_left]
  return idxs

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

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

  for s_idx in search_idx_options(S, A, x):
    if s_idx >= A: continue
    for t_idx in search_idx_options(T, B, S[s_idx]):
      if t_idx >= B: continue
      ans_list.append(abs(x-S[s_idx]) + abs(S[s_idx]-T[t_idx]))

  for t_idx in search_idx_options(T, B, x):
    if t_idx >= B: continue
    for s_idx in search_idx_options(S, A, T[t_idx]):
      if s_idx >= A: continue
      ans_list.append(abs(x-T[t_idx]) + abs(T[t_idx]-S[s_idx]))
 
  print(min(ans_list))

Submission status: Accepted

Solution code:
import bisect
def check(x,s,t):
    s_index = bisect.bisect_left(s,x)
    
    sr = s[s_index]
    sl = s[s_index-1]
    t_index = bisect.bisect_left(t,x)
    tr = t[t_index]
    tl = t[t_index-1]
    shrine = [sr,sl]
    temp = [tr,tl]
    ans = 10**20
    for i in range(2):
        for j in range(2):
            for l in range(2):
                if i == 0:
                    can = abs(shrine[j]-x)
                    can += abs(temp[l]-shrine[j])
                else:
                    can = abs(temp[l]-x)
                    can += abs(shrine[j]-temp[l])
                ans = min(ans,can)
    print(ans)
    


def main():
    a,b,q = map(int,input().split())
    s = [int(input()) for _ in range(a)]
    s.append(10**20)
    s.insert(0,-10**20)
    t = [int(input()) for _ in range(b)]
    t.append(10**20)
    t.insert(0,-10**20)
    x = [int(input()) for _ in range(q)]

    for i in range(q):
        check(x[i],s,t)

if __name__ == "__main__":
    main()