Problem:


Score : 400 points

Problem Statement

Along a road running in an east-west direction, there are A shrines and B temples.
The i-th shrine from the west is located at a distance of s_i meters from the west end of the road, and the i-th temple from the west is located at a distance of t_i meters from the west end of the road.

Answer the following Q queries:

Query i (1 \leq i \leq Q): If we start from a point at a distance of x_i meters from the west end of the road and freely travel along the road, what is the minimum distance that needs to be traveled in order to visit one shrine and one temple? (It is allowed to pass by more shrines and temples than required.)

Constraints

1 \leq A, B \leq 10^5

1 \leq Q \leq 10^5

1 \leq s_1 < s_2 < ... < s_A \leq 10^{10}

1 \leq t_1 < t_2 < ... < t_B \leq 10^{10}

1 \leq x_i \leq 10^{10}

s_1, ..., s_A, t_1, ..., t_B, x_1, ..., x_Q are all different.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B Q
s_1
:
s_A
t_1
:
t_B
x_1
:
x_Q

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

2 3 4
100
600
400
900
1000
150
2000
899
799

Sample Output 1

350
1400
301
399

There are two shrines and three temples. The shrines are located at distances of 100, 600 meters from the west end of the road, and the temples are located at distances of 400, 900, 1000 meters from the west end of the road.

Query 1: If we start from a point at a distance of 150 meters from the west end of the road, the optimal move is first to walk 50 meters west to visit a shrine, then to walk 300 meters east to visit a temple.

Query 2: If we start from a point at a distance of 2000 meters from the west end of the road, the optimal move is first to walk 1000 meters west to visit a temple, then to walk 400 meters west to visit a shrine. We will pass by another temple on the way, but it is fine.

Query 3: If we start from a point at a distance of 899 meters from the west end of the road, the optimal move is first to walk 1 meter east to visit a temple, then to walk 300 meters west to visit a shrine.

Query 4: If we start from a point at a distance of 799 meters from the west end of the road, the optimal move is first to walk 199 meters west to visit a shrine, then to walk 200 meters west to visit a temple.

Sample Input 2

1 1 3
1
10000000000
2
9999999999
5000000000

Sample Output 2

10000000000
10000000000
14999999998

The road is quite long, and we may need to travel a distance that does not fit into a 32-bit integer.



Sample input:
2 3 4
100
600
400
900
1000
150
2000
899
799


Sample output:
350
1400
301
399

Submission status: Time Limit Exceeded

Solution code:
A,B,Q = map(int, input().split())
inf = float("inf")
S = [-inf] + [ int(input()) for _ in range(A)] + [inf]
T = [-inf] + [ int(input()) for _ in range(B)] + [inf]
# jinja = [-inf] + [ int(input()) for _ in range(A)] + [inf]
# tera = [-inf] + [ int(input()) for _ in range(B)] + [inf]
X = [ int(input()) for _ in range(Q)]

from bisect import bisect_left, bisect_right

# for i in range(Q):
#     q = X[i]
#     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),
for q in range(Q):
    x = X[q]

    i = bisect_left(S, x)
    j = bisect_left(T, x)
    left_S , right_S =  x - S[i-1], S[i] - x
    left_T , right_T =  x - T[j-1], T[j] - x

    res = min( 
            max(left_S, left_T),
            left_S + right_T + min(left_S, right_T),
            right_S + left_T + min(right_S, left_T),
            max(right_S, right_T) 
            )
    print(res)

Submission status: Time Limit Exceeded

Solution code:
def calc(locate, start_point):
    if start_point <= min(locate):
        if locate[0] >= locate[shrine_no]: 
            print(locate[0] - start_point)
        else:
            print(locate[shrine_no] - start_point)
            
    elif start_point >= max(locate):
        if locate[shrine_no -1] >= locate[-1]:
            print(start_point - locate[-1])
        else:
            print(start_point - locate[shrine_no - 1])
            
    else:
        s_diff_list = []
        t_diff_list = []
            
        s_diff = start_point - locate[0]
        t_diff = start_point - locate[shrine_no]
        for i in range(shrine_no):
            s_diff_list.append(start_point - locate[i])
            if abs(s_diff) > abs(start_point - locate[i]):
                s_diff = start_point - locate[i]
        sort_s_diff = sorted(s_diff_list)
                
        for i in range(shrine_no, shrine_no + temple_no):
            t_diff_list.append(start_point - locate[i])
            if abs(t_diff) > abs(start_point - locate[i]):
                t_diff = start_point - locate[i]
        sort_t_diff = sorted(t_diff_list)
      
        if s_diff * t_diff < 0:
            dist = []
            for i in range(len(s_diff_list)):
                for j in range(len(t_diff_list)):
                    dist.append(abs(s_diff_list[i]-t_diff_list[j]) + min(abs(s_diff_list[i]), abs(t_diff_list[j])))
            print(min(dist))
            
        elif s_diff * t_diff > 0:
            print(max(abs(s_diff), abs(t_diff)))
        else:
            print(abs(s_diff+t_diff))

shrine_no, temple_no, q = map(int, input().split())
locate = []
start = []

for i in range(shrine_no+temple_no+q):
    tmp = int(input())
    if i < shrine_no+temple_no:
        locate.append(tmp)
    else:
        start.append(tmp)

for i in range(len(start)):
    calc(locate, start[i])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
A, B, Q = map(int, input().split())
BIG = 10**10 + 1
S = [-BIG] + [int(input()) for _ in range(A)] + [BIG*2]
T = [-BIG] + [int(input()) for _ in range(B)] + [BIG*2]
for _ in range(Q):
  x = int(input())
  shrine_b = bisect_right(S, x)
  dsl = x-S[shrine_b-1]
  dsr = S[shrine_b]-x
  temple_b = bisect_right(T, x)
  dtl = x-T[temple_b-1]
  dtr = T[temple_b]-x

  print(min(
    dsl if dsl > dtl else dtl,
    dsr if dsr > dtr else dtr,
    dsl * 2 + dtr,
    dsl + dtr * 2,
    dsr * 2 + dtl,
    dsr + dtl * 2
  ))

Submission status: Time Limit Exceeded

Solution code:
A, B, Q = list(map(int, raw_input().split()))

jinja = list()
for a in xrange(A): jinja.append(long(raw_input()))
tera = list()
for b in xrange(B): tera.append(long(raw_input()))

max_val = 10000000000000000.0

for q in xrange(Q):
    question = long(raw_input())
    if jinja[0] >= question:
        min_jinja = max_val
        max_jinja = jinja[0] - question
    elif jinja[-1] <= question:
        min_jinja = question - jinja[-1]
        max_jinja = max_val
    else:
        for a in xrange(A-1):
            if jinja[a] <= question and jinja[a+1] >= question:
                min_jinja = question - jinja[a]
                max_jinja = jinja[a+1] - question
    if tera[0] >= question:
        min_tera = max_val
        max_tera = tera[0] - question
    elif tera[-1] <= question:
        min_tera = question - tera[-1]
        max_tera = max_val
    else:
        for b in xrange(B-1):
            if tera[b] <= question and tera[b+1] >= question:
                min_tera = question - tera[b]
                max_tera =  tera[b+1] - question

    if max_tera == max_val and max_jinja == max_val:
        if min_jinja >= min_tera: print min_jinja
        else: print min_tera
    elif min_tera == max_val and min_jinja == max_val:
        if max_jinja >= max_tera: print max_jinja
        else: print max_tera
    elif min_jinja > min_tera and max_tera < max_jinja:
        if min_jinja >= max_jinja: print max_jinja
        else: print min_jinja
    elif min_tera < min_jinja and min_jinja < max_tera:
        if min_tera >= max_tera: print max_tera
        else: print min_tera
    elif min_tera <= min_jinja:
        print min(min_jinja, min_tera*2 + max_jinja, min_tera + max_jinja*2, max_tera)
    elif min_jinja <= min_tera:
        print min(min_tera, min_jinja*2 + max_tera, min_jinja + max_tera*2, max_jinja)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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 = np.array(s)
t = np.array(t)
for i in range(q):
  x = int(input())
  toS = np.abs(s - x)
  toT = np.abs(t - x)
  toSarg = np.argmin(toS)
  toTarg = np.argmin(toT)
  toSmin = abs(toS[toSarg])
  toTmin = abs(toT[toTarg])
  toStoT = np.abs(t - s[toSarg])
  toTtoS = np.abs(s - t[toTarg])
  toStoTmin = np.min(toStoT)
  toTtoSmin = np.min(toTtoS)
  print(min(toSmin + toStoTmin, toTmin + toTtoSmin))

Submission status: Time Limit Exceeded

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 = 10**12

def binary_search(query, arr):
    arr = [-INF] + arr + [INF]
    low = 0
    high = len(arr)
    t = (low+high)//2
    while low<high-1:
        if query>arr[t]:
            low = t
        else:
            high = t
        t = (low+high)//2
    return arr[low], arr[high]

def find(query):
    s1, s2 = binary_search(query, S)
    t1, t2 = binary_search(query, T)
    return s1, s2, t1, t2

def main():
    for x in X:
        s1, s2, t1, t2 = find(x)
        ss = [s1, s2]
        tt = [t1, t2]
        ans = INF
        for s in ss:
            for t in tt:
                d1 = abs(t-x) + abs(s-t)
                d2 = abs(s-x) + abs(t-s)
                ans = min(ans, d1, d2)
        print(ans)
    return

main()

Submission status: Time Limit Exceeded

Solution code:
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 i in range(Q):
	x = int(input())
	ids = bisect.bisect_left(S,x)
	idt = bisect.bisect_left(T,x)
	ans = 0
	sl = -10000000000000000
	sr = 10000000000000000
	tl = -10000000000000000
	tr = 10000000000000000
	if ids!=0:
		sl = S[ids-1]
	if ids!=A:
		sr = S[ids]
	if idt!=0:
		tl = T[idt-1]
	if idt!=B:
		tr = T[idt]
	ans = min(max(sr,tr)-x,x-min(sl,tl))
	ans = min(ans,2*abs(x-sl)+abs(x-tr),abs(x-sl)+2*abs(x-tr),2*abs(x-sr)+abs(x-tl),abs(x-sr)+2*abs(x-tl))
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
A, B, Q = map(int,input().split())
s_list = np.array([int(input()) for i in range(A)])
t_list = np.array([int(input()) for i in range(B)])
x_list = np.array([int(input()) for i in range(Q)])

def get_dist_to_first_cp(x,li):
    dist1 = li -x
    abs_dist1 = abs(dist1)
    dist_to_first_cp = min(abs_dist1)
    first_cp_num = np.argmin(abs_dist1)
    first_cp_pos = x + dist1[first_cp_num]
    return dist_to_first_cp, first_cp_pos
    


u_list = np.hstack((s_list,t_list))
for x in x_list:
    # shrine first
    dist_to_first_cp, first_cp_pos = get_dist_to_first_cp(x,s_list)
    dist2 = abs(np.array(t_list) - first_cp_pos)
    dist_to_sec_cp = min(dist2)
    ans_s = dist_to_first_cp + dist_to_sec_cp
    # temple first
    dist_to_first_cp, first_cp_pos = get_dist_to_first_cp(x,t_list)
    dist2 = abs(np.array(s_list) - first_cp_pos)
    dist_to_sec_cp = min(dist2)
    
    ans_t = dist_to_first_cp + dist_to_sec_cp

    print(min(ans_s,ans_t))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

def main():
  N_a, N_b, N_q = map(int, input().strip().split(' '))
  As = list(map(int, [input().strip() for _ in range(N_a)]))
  Bs = list(map(int, [input().strip() for _ in range(N_b)]))
  Qs = list(map(int, [input().strip() for _ in range(N_q)]))

  for q in Qs:
    min_a_l = -(2*(10**10)+1)
    min_b_l = -(2*(10**10)+1)
    min_a_r = 2*(10**10)+1
    min_b_r = 2*(10**10)+1
    for a in As:
      da = a - q
      if 0 <= da < min_a_r:
          min_a_r = da
      if 0 > da >= min_a_l:
          min_a_l = da

    for b in Bs:
      db = b - q
      if 0<= db < min_b_r:
          min_b_r = db
      if 0 > db >= min_b_l:
          min_b_l = db
    score = min([
      min_a_r if min_a_r > min_b_r else min_b_r,
      abs(min_a_l) if min_a_l < min_b_l else abs(min_b_l),
      2*min_a_r + abs(min_b_l) if min_a_r < abs(min_b_l) else min_a_r + 2*abs(min_b_l),
      2*abs(min_a_l) + abs(min_b_r) if abs(min_a_l) < abs(min_b_r) else abs(min_a_l) + 2*abs(min_b_r)])
    print(score)

  pass

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
A, B, Q = map(int, input().split())
BIG = 10**10 + 1
S = [-BIG] + [int(input()) for _ in range(A)] + [BIG*2]
T = [-BIG] + [int(input()) for _ in range(B)] + [BIG*2]
for _ in range(Q):
  x = int(input())
  shrine_b = bisect_left(S, x)
  dsl = x-S[shrine_b-1]
  dsr = S[shrine_b]-x
  temple_b = bisect_left(T, x)
  dtl = x-T[temple_b-1]
  dtr = T[temple_b]-x

  print(min(
    dsl if dsl > dtl else dtl,
    dsr if dsr > dtr else dtr,
    dsl * 2 + dtr,
    dsl + dtr * 2,
    dsr * 2 + dtl,
    dsr + dtl * 2
  ))

Submission status: Time Limit Exceeded

Solution code:
a,b,q = map(int,input().split())
A = [int(input()) for i in range(a)]
B = [int(input()) for i in range(b)]
Q = [int(input()) for i in range(q)]
for x in Q:
    ans1 = min([abs(z - w[0]) + w[1] for z in B for w in [[y,abs(x-y)] for y in A]])
    ans2 = min([abs(z - w[0]) + w[1] for z in A for w in [[y,abs(x-y)] for y in B]])
    print(min(ans1,ans2))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
A, B, Q = list(map(int, input().split()))
s = [int(input()) for i in range(A)]
t = [int(input()) for i in range(B)]
s.append(-100000000000);s.append(100000000000)
t.append(-100000000000);t.append(100000000000)
s = sorted(s, reverse=False)
t = sorted(t, reverse=False)
sn = np.array(s)
tn = np.array(t)

for i in range(Q):
    xi = int(input())
    sr = sn[sn.searchsorted(xi)]
    sl = sn[sn.searchsorted(xi) - 1]
    tr = tn[tn.searchsorted(xi)]
    tl = tn[tn.searchsorted(xi) - 1]

    ans = min(max(sr, tr) - xi, xi - min(sl, tl),
              tr - sl + min(tr - xi, xi - sl), sr - tl + min(sr - xi, xi - tl))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
A,B,Q=map(int,input().split())
s=[]
t=[]
for i in range(A):
  s.append(int(input()))
for i in range(B):
  t.append(int(input()))
for i in range(Q):
  x=int(input())
  s1=s[:]
  s1.append(x)
  s1.sort()
  j=s1.index(x)
  if j==0:
    kouhoA=[s[j]]
  elif j==A:
    kouhoA=[s[j-1]]
  else:
    kouhoA=[s[j],s[j-1]]
  t1=t[:]
  t1.append(x)
  t1.sort()
  k=t1.index(x)
  if k==0:
    kouhoB=[t[k]]
  elif k==B:
    kouhoB=[t[k-1]]
  else:
    kouhoB=[t[k],t[k-1]]
  if len(kouhoA)==1:
    
    if len(kouhoB)==1:
      a=abs(kouhoA[0]-kouhoB[0])
      ans=min([abs(x-kouhoA[0])+a,abs(x-kouhoB[0])+a])
    else:
      u=abs(x-kouhoA[0])
      a=abs(kouhoA[0]-kouhoB[0])
      b=abs(kouhoA[0]-kouhoB[1])
      ans=min([u+a,abs(x-kouhoB[0])+a,u+b,abs(x-kouhoB[1])+b])
  else:
    if len(kouhoB)==1:
      a=abs(kouhoA[0]-kouhoB[0])
      c=abs(kouhoB[0]-kouhoA[1])
      v=abs(x-kouhoB[0])
      ans=min([abs(x-kouhoA[0])+a,v+a,abs(x-kouhoA[1])+c,v+c])
    else:
      u=abs(x-kouhoA[0])
      a=abs(kouhoA[0]-kouhoB[0])
      b=abs(kouhoA[0]-kouhoB[1])
      c=abs(kouhoB[0]-kouhoA[1])
      d=abs(kouhoA[1]-kouhoB[1])
      v=abs(x-kouhoB[0])
      w=abs(x-kouhoA[1])
      y=abs(x-kouhoB[1])
      ans=min([u+a,v+a,w+d,y+d,w+c,v+c,u+b,y+b])
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
A, B, Q = list(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_min = A-1
    for i in range(A):
        if s[i] > x:
            s_min = i-1
            break
    t_min = B-1
    for i in range(B):
        if t[i] > x:
            t_min = i-1
            break

    if s_min == -1:
        if t_min == -1:
            print(max(s[0]-x, t[0]-x))
        elif t_min == B-1:
            print(s[0]-t[t_min]+min(s[0]-x, t[t_min]-x))
        else:
            print(min(t[t_min+1]-x, s[0]-t[t_min]+min(s[0]-x, t[t_min]-x)))
    elif s_min == A-1:
        if t_min == -1:
            print(t[0]-s[s_min] + min(t[0]-x, x-s[s_min]))
        elif t_min == B-1:
            print(max(x-s[s_min], x-t[t_min]))
        else:
            print(min(x-t[t_min], t[t_min+1]-s[s_min] + min(t[t_min+1]-x, x-s[s_min])))
    else:
        if t_min == -1:
            if t[0] < s[s_min+1]:
                print(min(s[s_min + 1] - x, t[0] - s[s_min] + min(t[0] - x, x-s[s_min])))
            else:
                print(t[0]-x)
        elif t_min == B-1:
            print(min(x - s[s_min], s[s_min + 1] - t[t_min] + min(s[s_min + 1] - x, x - t[t_min])))
        else:
            if s[s_min] < t[t_min]:
                if s[s_min+1] < t[t_min+1]:
                    print(min(x-s[s_min], t[t_min+1] - x, s[s_min+1] - t[t_min] + min(x-t[t_min], s[s_min+1]-x)))
                else:
                    print(min(x-s[s_min], s[s_min+1]-x))
            else:
                if s[s_min+1] < t[t_min+1]:
                    print(min(t[t_min+1]-x, x-t[t_min]))
                else:
                    print(min(x-t[t_min], s[s_min+1] - x, t[t_min+1] - s[s_min] + min(x-s[s_min], t[t_min+1]-x)))

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return list(sys.stdin.readline())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007

#A

#B

#C
"""
n,a,b,c = LI()
l = IR(n)
f = [True for i in range(3)]
ans = 0
for i in range(n):
    for d in range(3):
        if abs(l[i]-[a,b,c][d]) <= 10 and f[d]:
            ans += abs(l[i]-[a,b,c][d])
            f[d] = False
            l[i] = -float("inf")
k = False
for i in f:
    if i:
        k = True
        break
if not k:
    print(ans)
    quit()
"""
#D
a,b,q = LI()
s = IR(a)
t = IR(b)
for i in range(q):
    x = I()
    c = bisect.bisect_left(s,x)
    ans = float("inf")
    if c == a:
        k = abs(x-s[-1])
        y = s[-1]
        d = bisect.bisect_left(t,y)
        if d == b:
            k += abs(y-t[-1])
        else:
            if abs(y-t[d-1]) < abs(y-t[d]):
                k += abs(y-t[d-1])
            else:
                k += abs(y-t[d])
        ans = min(k,ans)
    else:
        k = abs(x-s[c-1])
        y = s[c-1]
        d = bisect.bisect_left(t,y)
        if d == b:
            k += abs(y-t[-1])
        else:
            if abs(y-t[d-1]) < abs(y-t[d]):
                k += abs(y-t[d-1])
            else:
                k += abs(y-t[d])
        ans = min(k,ans)
        k = abs(x-s[c])
        y = s[c]
        d = bisect.bisect_left(t,y)
        if d == b:
            k += abs(y-t[-1])
        else:
            if abs(y-t[d-1]) < abs(y-t[d]):
                k += abs(y-t[d-1])
            else:
                k += abs(y-t[d])
        ans = min(k,ans)
    c = bisect.bisect_left(t,x)
    if c == b:
        k = abs(x-t[-1])
        y = t[-1]
        d = bisect.bisect_left(s,y)
        if d == a:
            k += abs(y-s[-1])
        else:
            if abs(y-s[d-1]) < abs(y-s[d]):
                k += abs(y-s[d-1])
            else:
                k += abs(y-s[d])
        ans = min(k,ans)
    else:
        k = abs(x-t[c-1])
        y = t[c-1]
        d = bisect.bisect_left(s,y)
        if d == a:
            k += abs(y-s[-1])
        else:
            if abs(y-s[d-1]) < abs(y-s[d]):
                k += abs(y-s[d-1])
            else:
                k += abs(y-s[d])
        ans = min(k,ans)
        k = abs(x-t[c])
        y = t[c]
        d = bisect.bisect_left(s,y)
        if d == a:
            k += abs(y-s[-1])
        else:
            if abs(y-s[d-1]) < abs(y-s[d]):
                k += abs(y-s[d-1])
            else:
                k += abs(y-s[d])
        ans = min(k,ans)
    print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Time Limit Exceeded

Solution code:
num=list(map(int,input().split()))
s_list = [int(input()) for i in range(num[0])]
t_list = [int(input()) for i in range(num[1])]
x_list = [int(input()) for i in range(num[2])]

for x_ in x_list:
	min_s=min(list(map(lambda x: abs(x-x_), s_list)))
	min_t=min(list(map(lambda x: abs(x-x_), t_list)))
	
	min_index_t=list(map(lambda x: abs(x-x_), t_list)).index(min_t)
	
	minmin_t=min(list(map(lambda x: abs(x-t_list[min_index_t]), s_list)))+min_t




	min_index_s=list(map(lambda x: abs(x-x_), s_list)).index(min_s)
	minmin_s=min(list(map(lambda x: abs(x-s_list[min_index_s]), t_list)))+min_s
	print(min(minmin_t,minmin_s))

Submission status: Time Limit Exceeded

Solution code:
A, B, Q = map(int, input().split())
shrine = [int(input()) for i in range(A)]
temple = [int(input()) for i in range(B)]

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

Submission status: Time Limit Exceeded

Solution code:
A, B, Q = map(int, input().split())
S, T =[None] * (A+2), [None] * (B+2)
S[0], T[0] = -10**20, -10**20
for i in range(A):
    S[i+1] = int(input())
for i in range(B):
    T[i+1] = int(input())
S[-1] = 10**20
T[-1] = 10**20

def Bsearch(x, L, lenL):
    low, high = 0, lenL
    while high-low > 1:
        mid = (low+high)//2
        if L[mid] > x:
            high = mid
        else: low = mid
    return [x-L[low], L[low+1]-x]

lenS, lenT = len(S), len(T)
for _ in range(Q):
    x = int(input())
    sLength0, sLength1 = Bsearch(x, S, lenS)
    tLength0, tLength1 = Bsearch(x, T, lenT)
    Ans = (max(sLength0, tLength0), max(sLength1, tLength1), sLength0 + tLength1 + min(sLength0, tLength1), sLength1 + tLength0 + min(sLength1, tLength0))
    print(min(Ans))

Submission status: Time Limit Exceeded

Solution code:
A, B, Q = map(int, input().split())
ss = []
ts = []
xs = []

for _ in range(A):
    ss.append(int(input()))

for _ in range(B):
    ts.append(int(input()))

for _ in range(Q):
    xs.append(int(input()))

import numpy as np

ss = np.array(ss)
ts = np.array(ts)

def near(l, v):
    diff = l - v
    absd = np.abs(diff)
    idx = absd.argmin()
    if diff[idx] > 0:
        if idx == 0:
            return None, absd[idx]
        else:
            return absd[idx-1], absd[idx]
    else:
        if idx+1 == len(l):
            return absd[idx], None
        else:
            return absd[idx], absd[idx+1]

for x in xs:
    sl, sh = near(ss, x)
    tl, th = near(ts, x)

    try:
        p1 = max(sl, tl)
    except:
        p1 = 10e11

    try:
        p2 = max(sh, th)
    except:
        p2 = 10e11

    try:
        p3 = 2*sl + th if sl < th else sl + 2*th
    except:
        p3 = 10e11

    try:
        p4 = 2*tl + sh if tl < sh else tl + 2*sh
    except:
        p4 = 10e11

    print(min(p1, p2, p3, p4))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from functools import lru_cache

A, B, Q = map(int, input().split())
adisps = np.array([int(input()) for _ in range(A)])
bdisps = np.array([int(input()) for _ in range(B)])
qdisps = np.array([int(input()) for _ in range(Q)])

@lru_cache(maxsize=100000)
def nearest(now, flag):
    disps = adisps if flag == 0 else bdisps
    idx = np.argmin(np.abs(disps - now))
    nearest_point = disps[idx]
    cost = np.abs(now - nearest_point)
    return nearest_point, cost

for qdisp in qdisps:

    #A→B
    pos_a1, cost_a1 = nearest(qdisp, 0)
    pos_b1, cost_b1 = nearest(pos_a1, 1)
    cost1 = cost_a1 + cost_b1

    #B→A
    pos_b2, cost_b2 = nearest(qdisp, 1)
    pos_a2, cost_a2 = nearest(pos_b2, 0)
    cost2 = cost_a2 + cost_b2

    ans = min(cost1, cost2)
    print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import copy


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

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

S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]

H = {}
Y = copy.copy(X)

Y.sort()

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

for x in X:
    print(H[x])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

hint = list(map(int, input().split()))
s = [int(input()) for i in range(sum(hint))]
# print(s)

a = np.asarray(s[:hint[0]])
b = np.asarray(s[hint[0]:-hint[2]])
sum = 0
for t in s[-hint[2]:]:
    a_dis = np.argmin(np.abs(a - t))
    b_dis = np.argmin(np.abs(b - t))
    print(np.min([np.abs(b[b_dis] - t) + np.min(np.abs(a[np.max([a_dis-1,0]):a_dis+1] - b[b_dis])), np.abs(a[a_dis] - t) + np.min(np.abs(b[np.max([b_dis-1,0]):b_dis+1] - a[a_dis]))]))

Submission status: Time Limit Exceeded

Solution code:
a,b,q = map(int,input().split())
A = [int(input()) for i in range(a)]
B = [int(input()) for i in range(b)]
Q = [int(input()) for i in range(q)]
for x in Q:
  l = []
  for y in A:
    l.append([y,abs(x-y)])
    ans1 = min([abs(z - w[0]) + w[1] for z in B for w in l])
  l = []
  for y in B:
    l.append([y,abs(x-y)])
    ans2 = min([abs(z - w[0]) + w[1] for z in A for w in l])
  print(min(ans1,ans2))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from functools import lru_cache

A, B, Q = map(int, input().split())
adisps = np.array([int(input()) for _ in range(A)])
bdisps = np.array([int(input()) for _ in range(B)])
qdisps = np.array([int(input()) for _ in range(Q)])

@lru_cache(maxsize=1000)
def nearest(now, flag):
    disps = adisps if flag == 0 else bdisps
    idx = np.argmin(np.abs(disps - now))
    nearest_point = disps[idx]
    cost = np.abs(now - nearest_point)
    return nearest_point, cost

for qdisp in qdisps:

    #A→B
    pos_a1, cost_a1 = nearest(qdisp, 0)
    pos_b1, cost_b1 = nearest(pos_a1, 1)
    cost1 = cost_a1 + cost_b1

    #B→A
    pos_b2, cost_b2 = nearest(qdisp, 1)
    pos_a2, cost_a2 = nearest(pos_b2, 0)
    cost2 = cost_a2 + cost_b2

    ans = min(cost1, cost2)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor

import heapq
import itertools
import operator


inf = float('inf')


def get_int():
    return int(input())


def get_str():
    return input().strip()


def get_list_of_int():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())


# inputs
A, B, Q = 0, 0, 0
S = []
T = []
X = []


def set_inputs():
    global A, B, Q, S, T, X
    A, B, Q = get_list_of_int()
    for _ in range(A):
        S.append(get_int())
    for _ in range(B):
        T.append(get_int())
    for _ in range(Q):
        X.append(get_int())


def main():
    set_inputs()

    for i in range(Q):
        ns = abs(max([S[j] - X[i] for j in range(A) if S[j] - X[i] <= 0] + [-inf]))
        ps = abs(min([S[j] - X[i] for j in range(A) if S[j] - X[i] >= 0] + [inf]))
        nt = abs(max([T[j] - X[i] for j in range(B) if T[j] - X[i] <= 0] + [-inf]))
        pt = abs(min([T[j] - X[i] for j in range(B) if T[j] - X[i] >= 0] + [inf]))
        print(min(max(ns, nt), max(ps, pt), ns * 2 + pt, ns + pt * 2, nt * 2 + ps, nt + ps * 2))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
A, B, Q = map(int, input().split())
BIG = 10**10 + 1
S = [-BIG] + [int(input()) for _ in range(A)] + [BIG*2]
T = [-BIG] + [int(input()) for _ in range(B)] + [BIG*2]
S.sort()
T.sort()
for _ in range(Q):
  x = int(input())
  shrine_b = bisect_left(S, x)
  dsl = x-S[shrine_b-1]
  dsr = S[shrine_b]-x
  temple_b = bisect_left(T, x)
  dtl = x-T[temple_b-1]
  dtr = T[temple_b]-x

  print(min(
    dsl if dsl > dtl else dtl,
    dsr if dsr > dtr else dtr,
    dsl * 2 + dtr,
    dsl + dtr * 2,
    dsr * 2 + dtl,
    dsr + dtl * 2
  ))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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 = np.array(s)
t = np.array(t)
for i in range(q):
  x = int(input())
  toS = np.abs(s - x)
  toT = np.abs(t - x)
  toSarg = np.argmin(toS)
  toTarg = np.argmin(toT)
  toSmin = np.min(toS)
  toTmin = np.min(toT)
  toStoT = np.abs(t - s[toSarg])
  toTtoS = np.abs(s - t[toTarg])
  toStoTmin = np.min(toStoT)
  toTtoSmin = np.min(toTtoS)
  print(min(toSmin + toStoTmin, toTmin + toTtoSmin))

Submission status: Time Limit Exceeded

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

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