結果

問題 No.3072 Speedrun Query
ユーザー 👑 loop0919
提出日時 2025-03-21 22:21:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,275 ms / 2,500 ms
コード長 1,510 bytes
コンパイル時間 281 ms
コンパイル使用メモリ 82,364 KB
実行使用メモリ 169,996 KB
最終ジャッジ日時 2025-03-21 22:22:12
合計ジャッジ時間 20,027 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #

from heapq import merge
import sys
from bisect import bisect_left

input = sys.stdin.readline
INF = float("inf")

N, K_A, K_B = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))

merged = list(merge([(a, "a") for a in a_list], [(b, "b") for b in b_list]))
min_val = float("inf")

for i in range(K_A + K_B - 1):
    x, flg_x = merged[i]
    y, flg_y = merged[i + 1]
    if flg_x == flg_y:
        continue
    min_val = min(min_val, abs(x - y))

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    
    dist_a_s = INF
    idx_a_s = bisect_left(a_list, s)
    for i in range(max(0, idx_a_s - 1), min(K_A, idx_a_s + 2)):
        dist_a_s = min(dist_a_s, abs(a_list[i] - s))
    
    dist_a_t = INF
    idx_a_t = bisect_left(a_list, t)
    for i in range(max(0, idx_a_t - 1), min(K_A, idx_a_t + 2)):
        dist_a_t = min(dist_a_t, abs(a_list[i] - t))
    
    dist_b_s = INF
    idx_b_s = bisect_left(b_list, s)
    for i in range(max(0, idx_b_s - 1), min(K_B, idx_b_s + 2)):
        dist_b_s = min(dist_b_s, abs(b_list[i] - s))
    
    dist_b_t = INF
    idx_b_t = bisect_left(b_list, t)
    for i in range(max(0, idx_b_t - 1), min(K_B, idx_b_t + 2)):
        dist_b_t = min(dist_b_t, abs(b_list[i] - t))
    
    ans = abs(s - t)
    ans = min(ans, dist_a_s + dist_a_t)
    ans = min(ans, dist_b_s + dist_b_t)
    ans = min(ans, dist_a_s + min_val + dist_b_t)
    ans = min(ans, dist_b_s + min_val + dist_a_t)
    print(ans)

0