結果

問題 No.3072 Speedrun Query
コンテスト
ユーザー i_taku
提出日時 2025-03-26 10:26:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,162 ms / 2,500 ms
コード長 1,487 bytes
コンパイル時間 358 ms
コンパイル使用メモリ 82,748 KB
実行使用メモリ 185,580 KB
最終ジャッジ日時 2025-03-26 10:27:05
合計ジャッジ時間 26,611 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

def bfs01(A, s):
    dist = [1 << 60] * (N + 2)
    dist[s] = 0
    que = deque([s])
    while que:
        v = que.popleft()
        for nv in g[v]:
            if nv >= N or v >= N:
                if dist[nv] > dist[v]:
                    dist[nv] = dist[v]
                    que.appendleft(nv)
            else:
                if dist[nv] > dist[v] + 1:
                    dist[nv] = dist[v] + 1
                    que.append(nv)
    return dist

N, KA, KB = map(int, input().split())
A = [int(x) - 1 for x in input().split()]
B = [int(x) - 1 for x in input().split()]

g = [[] for _ in range(N + 2)]
for i in range(N - 1):
    g[i].append(i + 1)
    g[i + 1].append(i)
for a in A:
    g[N].append(a)
    g[a].append(N)
for b in B:
    g[N + 1].append(b)
    g[b].append(N + 1)

distA = bfs01(A, N)

distB = bfs01(B, N + 1)

INF = 1 << 60
la = [-INF] * N
ra = [INF] * N
lb = [-INF] * N
rb = [INF] * N

i = 0
for a in A:
    while i <= a:
        ra[i] = a
        i += 1
i = N - 1
for a in A[::-1]:
    while i >= a:
        la[i] = a
        i -= 1
i = 0
for b in B:
    while i <= b:
        rb[i] = b
        i += 1
i = N - 1
for b in B[::-1]:
    while i >= b:
        lb[i] = b
        i -= 1    

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    s, t = s - 1, t - 1
    res1 = t - s
    res2 = min(s - la[s], ra[s] - s) + distA[t]
    res3 = min(s - lb[s], rb[s] - s) + distB[t]
    print(min(res1, res2, res3))
0