結果

問題 No.3072 Speedrun Query
コンテスト
ユーザー pengin_2000
提出日時 2025-03-21 22:54:01
言語 C
(gcc 15.2.0)
コンパイル:
gcc-15 -O2 -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
AC  
実行時間 461 ms / 2,500 ms
コード長 1,647 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 178 ms
コンパイル使用メモリ 39,372 KB
最終ジャッジ日時 2026-02-22 13:22:46
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<stdio.h>
int abs(int n)
{
	if (n < 0)
		n *= -1;
	return n;
}
int n, ka, kb;
int a[300005], b[300005];
int id_a(int v)
{
	int min, mid, max;
	min = -1;
	max = ka;
	while (max - min > 1)
	{
		mid = (max + min) / 2;
		if (a[mid] < v)
			min = mid;
		else
			max = mid;
	}
	if (min < 0)
		return a[max];
	else if (max == ka)
		return a[min];
	else if (v - a[min] < a[max] - v)
		return a[min];
	else
		return a[max];
}
int id_b(int v)
{
	int min, mid, max;
	min = -1;
	max = kb;
	while (max - min > 1)
	{
		mid = (max + min) / 2;
		if (b[mid] < v)
			min = mid;
		else
			max = mid;
	}
	if (min < 0)
		return b[max];
	else if (max == kb)
		return b[min];
	else if (v - b[min] < b[max] - v)
		return b[min];
	else
		return b[max];
}
int main()
{
	scanf("%d %d %d", &n, &ka, &kb);
	int i, j;
	for (i = 0; i < ka; i++)
	{
		scanf("%d", &a[i]);
		a[i]--;
	}
	for (i = 0; i < kb; i++)
	{
		scanf("%d", &b[i]);
		b[i]--;
	}
	int dist = abs(a[0] - b[0]);
	for (i = 0; i < ka; i++)
	{
		j = id_b(a[i]);
		if (dist > abs(a[i] - j))
			dist = abs(a[i] - j);
	}
	int q, s, t;
	scanf("%d", &q);
	int ans;
	for (; q > 0; q--)
	{
		scanf("%d %d", &s, &t);
		s--;
		t--;
		ans = t - s;
		i = id_a(s);
		j = id_a(t);
		if (ans > abs(s - i) + abs(t - j))
			ans = abs(s - i) + abs(t - j);
		i = id_b(s);
		j = id_b(t);
		if (ans > abs(s - i) + abs(t - j))
			ans = abs(s - i) + abs(t - j);
		i = id_a(s);
		j = id_b(t);
		if (ans > abs(s - i) + abs(t - j) + dist)
			ans = abs(s - i) + abs(t - j) + dist;
		i = id_b(s);
		j = id_a(t);
		if (ans > abs(s - i) + abs(t - j) + dist)
			ans = abs(s - i) + abs(t - j) + dist;
		printf("%d\n", ans);
	}
	return 0;
}
0