結果
問題 | No.3072 Speedrun Query |
ユーザー |
![]() |
提出日時 | 2025-03-21 22:45:33 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,351 ms / 2,500 ms |
コード長 | 2,042 bytes |
コンパイル時間 | 2,201 ms |
コンパイル使用メモリ | 79,700 KB |
実行使用メモリ | 105,336 KB |
最終ジャッジ日時 | 2025-03-21 22:46:00 |
合計ジャッジ時間 | 21,716 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] sa = br.readLine().split(" "); int n = Integer.parseInt(sa[0]); int ka = Integer.parseInt(sa[1]); int kb = Integer.parseInt(sa[2]); sa = br.readLine().split(" "); int[] a = new int[ka + 2]; for (int i = 0; i < ka; i++) { a[i + 1] = Integer.parseInt(sa[i]); } a[0] = -10000000; a[ka + 1] = 10000000; sa = br.readLine().split(" "); int[] b = new int[kb + 2]; int min = n; for (int i = 0; i < kb; i++) { int e = Integer.parseInt(sa[i]); b[i + 1] = e; min = Math.min(min, getDist(e, a)); } b[0] = -10000000; b[kb + 1] = 10000000; int q = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); for (int i = 0; i < q; i++) { sa = br.readLine().split(" "); int s = Integer.parseInt(sa[0]); int t = Integer.parseInt(sa[1]); int ans = t - s; ans = Math.min(ans, getDist(s, a) + getDist(t, a)); ans = Math.min(ans, getDist(s, b) + getDist(t, b)); ans = Math.min(ans, getDist(s, a) + getDist(t, b) + min); ans = Math.min(ans, getDist(s, b) + getDist(t, a) + min); sb.append(ans).append("\n"); } br.close(); System.out.print(sb.toString()); } static int getDist(int e, int[] a) { int min = 100000000; int l = floor(a, e); min = Math.min(min, e - a[l]); int r = ceiling(a, e); min = Math.min(min, a[r] - e); return min; } static int ceiling(int[] array, int val) { int ok = array.length; int ng = -1; while (Math.abs(ok - ng) > 1) { int mid = (ok + ng) / 2; if (array[mid] >= val) { ok = mid; } else { ng = mid; } } return ok; } static int floor(int[] array, int val) { int ng = array.length; int ok = -1; while (Math.abs(ok - ng) > 1) { int mid = (ok + ng) / 2; if (array[mid] <= val) { ok = mid; } else { ng = mid; } } return ok; } }