結果

問題 No.3072 Speedrun Query
コンテスト
ユーザー norioc
提出日時 2025-03-22 07:08:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,097 ms / 2,500 ms
コード長 1,465 bytes
コンパイル時間 436 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 169,460 KB
最終ジャッジ日時 2025-03-22 07:08:51
合計ジャッジ時間 20,703 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
from itertools import pairwise

INF = 1 << 60
N, KA, KB = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
B = list(map(lambda x: int(x)-1, input().split()))


def calc_warp_dists(warps: list[int]) -> list[int]:
    dists = [INF] * N
    q = deque()
    for wi in warps:
        q.append(wi)
        dists[wi] = 0

    while q:
        wi = q.popleft()
        if wi > 0 and dists[wi-1] > dists[wi] + 1:
            dists[wi-1] = dists[wi] + 1
            q.append(wi-1)

        if wi+1 < N and dists[wi+1] > dists[wi] + 1:
            dists[wi+1] = dists[wi] + 1
            q.append(wi+1)

    return dists


a_warp_dists = calc_warp_dists(A)
b_warp_dists = calc_warp_dists(B)

ab_warp_dist = INF  # ワープ A, B 間の最短距離
ws = [(a, 0) for a in A] + [(b, 1) for b in B]
for (x, xt), (y, yt) in pairwise(sorted(ws)):
    if xt != yt:
        ab_warp_dist = min(ab_warp_dist, y - x)


def solve(s: int, t: int) -> int:
    # S -> T
    x1 = t - s
    # S -> A -> T
    x2 = a_warp_dists[s] + a_warp_dists[t]
    # S -> B -> T
    x3 = b_warp_dists[s] + b_warp_dists[t]
    # S -> A -> B -> T
    x4 = a_warp_dists[s] + ab_warp_dist + b_warp_dists[t]
    # S -> B -> A -> T
    x5 = b_warp_dists[s] + ab_warp_dist + a_warp_dists[t]

    return min(x1, x2, x3, x4, x5)


Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())

    res = solve(s, t)
    print(res)
0