結果
問題 |
No.3072 Speedrun Query
|
ユーザー |
👑 |
提出日時 | 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 |
ソースコード
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)