Tưới cây bằng vòi phun

Binary-search Buổi 13 — Chặt nhị phân đáp án sorting two-pointers
Points
18
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Trên một con đường thẳng có $N$ cây xanh nằm tại các tọa độ $a_1, a_2, \dots, a_N$ và $M$ vòi phun nước đặt tại các tọa độ $b_1, b_2, \dots, b_M$. Tất cả các vòi phun đều có cùng bán kính tưới $R$: một vòi phun tại vị trí $b_j$ có thể tưới được mọi cây tại vị trí $a_i$ thỏa mãn $|a_i - b_j| \le R$.

Hãy tìm bán kính $R$ nhỏ nhất (là số nguyên không âm) để mọi cây đều được ít nhất một vòi phun tưới tới.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $M$.
  • Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$.
  • Dòng thứ ba chứa $M$ số nguyên $b_1, b_2, \dots, b_M$.
Dữ liệu ra

In ra bán kính $R$ nhỏ nhất.

Ví dụ
Input Output
3 2

-2 2 4 -3 0 | 4 | | 5 1 1 2 3 4 5 3 | 2 |

Giới hạn
  • $1 \le N, M \le 10^5$
  • $-10^9 \le a_i, b_j \le 10^9$.
Draft saved