Problem: 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.)

Submission attempts (in order):
#!/usr/bin/env python3
import sys
 
 
def solve(n: int, m: int, Q: int, s: "List[int]", t: "List[int]", x: "List[int]"):
 
    def check_pos(target, a, x):
        ret = {}
        a_x = a + x
        a_x.sort()
        idx = 0
        while idx < len(a_x) and a_x[idx] < target[0]:
            dis = target[0] - a_x[idx]
            ret[a_x[idx]] = [dis, [target[0], dis]] 
            idx += 1
        for i in range(len(target) - 1):
            while idx < len(a_x) and target[i] <= a_x[idx] <= target[i + 1]:
                pos = a_x[idx]
                l = a_x[idx] - target[i]
                r = target[i + 1] - a_x[idx]
                ret[pos] = [
                    min(l, r),
                    [target[i],     l],
                    [target[i + 1], r]
                ]
                idx += 1
        while idx < len(a_x):
            dis = a_x[idx] - target[-1]
            ret[a_x[idx]] = [dis, [target[-1], dis]] 
            idx += 1
        return ret
 
    nearest_s = check_pos(s, t, x)
    nearest_t = check_pos(t, s, x)
    return
 
    for q in x:
        ret = min(
                min([(pos_dis[1] + nearest_t[pos_dis[0]][0]) for pos_dis in nearest_s[q][1:]]),
                min([(pos_dis[1] + nearest_s[pos_dis[0]][0]) for pos_dis in nearest_t[q][1:]]))
        print(ret)
    return
 
 
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]"
    solve(A, B, Q, s, t, x)
 
if __name__ == '__main__':
    main()

#!/usr/bin/env python3
import sys


def solve(n: int, m: int, Q: int, s: "List[int]", t: "List[int]", x: "List[int]"):

    def check_pos(target, a, x):
        ret = {}
        a_x = a + x
        a_x.sort()
        idx = 0
        while idx < len(a_x) and a_x[idx] < target[0]:
            pos = a_x[idx]
            ret[pos] = {
                'dis': target[0] - a_x[idx],
                'pos': [target[0]]
            }
            idx += 1
        for i in range(len(target) - 1):
            while idx < len(a_x) and target[i] <= a_x[idx] <= target[i + 1]:
                pos = a_x[idx]
                ret[pos] = {'dis': min(a_x[idx] - target[i], target[i + 1] - a_x[idx])}
                if a_x[idx] - target[i] == target[i + 1] - a_x[idx]:
                    ret[pos]['pos'] = [target[i], target[i + 1]]
                elif a_x[idx] - target[i] < target[i + 1] - a_x[idx]:
                    ret[pos]['pos'] = [target[i]]
                else:
                    ret[pos]['pos'] = [target[i + 1]]
                idx += 1
        while idx < len(a_x):
            pos = a_x[idx]
            ret[pos] = {
                'dis': a_x[idx] - target[-1],
                'pos': [target[-1]]
            }
            idx += 1
        return ret

    nearest_s = check_pos(s, t, x)
    nearest_t = check_pos(t, s, x)

    print('hoge')
    return

    for q in x:
        ret = min(nearest_s[q]['dis'] + min([nearest_t[pos]['dis'] for pos in nearest_s[q]['pos']]),
                  nearest_t[q]['dis'] + min([nearest_s[pos]['dis'] for pos in nearest_t[q]['pos']]))
        print(ret)
    return


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]"
    solve(A, B, Q, s, t, x)

if __name__ == '__main__':
    main()


#!/usr/bin/env python3
import sys


def solve(N: int, M: int, Q: int, s: "List[int]", t: "List[int]", x: "List[int]"):

    def binary_search(ary, val):
        n = len(ary)
        l = -1
        r = n
        while r - l > 1:
            mid = (l + r) // 2
            if ary[mid] >= val:
                r = mid
            else:
                l = mid
        if l == -1:
            return [ary[0]]
        if r == n:
            return [ary[n - 1]]
        return [ary[l], ary[r]]

    for q in x:
        ret = float('inf')
        a_pos = binary_search(s, q)
        b_pos = binary_search(t, q)
        for a in a_pos:
            for b in b_pos:
                ret = min(ret, abs(a - q) + abs(b - a))
                ret = min(ret, abs(b - q) + abs(a - b))
        print(ret)
    return


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]"
    solve(A, B, Q, s, t, x)

if __name__ == '__main__':
    main()


Verdicts: Wrong Answer

Wrong Answer

Accepted