結果

問題 No.3072 Speedrun Query
コンテスト
ユーザー ks2m
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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;
	}
}
0