Rabbits and Holes

Rabbits and Holes

Time limit: 1 s.
Memory limit: 256 MB

There are \(N\) rabbits positioned along a line in the jungle. They saw a big lion and they want to hide in their holes.

There are \(M\) holes on the same line, and each hole can accommodate any number of rabbits.

You are given the positions of the \(N\) rabbits and the \(M\) holes on the line, expressed in meters.

Calculate what is the shortest time needed for all the rabbits to hide in a hole. A rabbit runs at the speed of \(1\) meter per second.

Input

First line contains two integers \(N\), \(M\).

Second line contains \(N\) integers \(R_1, R_2, \dots, R_N\).

Third line contains \(M\) integers \(H_1, H_2, \dots, H_M\).

Output

A single integer, the shortest time all rabbits can hide in.

Scoring

Subtask Constraints Points
\(1\) \(N = 1, M = 1\) \(5\)
\(2\) \(N = 1\) \(12\)
\(3\) \(M = 1\) \(13\)
\(4\) All rabbits are to the left of all holes \(15\)
\(5\) \(N, M \le 1000\) \(20\)
\(6\) No additional constraints \(35\)

Constraints

  • \(1 \le N, M \le 10^5\)
  • \(1 \le R_i, H_i \le 10^9\)

Example

Input

4 5
30 60 10 20
25 80 50 10 70

Output

10
Solution

Holes have unlimited capacity, so every rabbit can independently choose its nearest hole. Sort the hole positions. For each rabbit, use lower_bound and check the first hole not to its left and the last hole to its left.

The answer is the maximum of these nearest distances. The complexity is \(O(M\log M+N\log M)\) time and \(O(M)\) memory.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<long long> rabbits(n), holes(m);
    for (long long& position : rabbits) cin >> position;
    for (long long& position : holes) cin >> position;

    sort(holes.begin(), holes.end());
    long long answer = 0;

    for (long long rabbit : rabbits) {
        auto it = lower_bound(holes.begin(), holes.end(), rabbit);
        long long nearest = (1LL << 60);

        if (it != holes.end()) {
            nearest = min(nearest, *it - rabbit);
        }
        if (it != holes.begin()) {
            nearest = min(nearest, rabbit - *prev(it));
        }

        answer = max(answer, nearest);
    }

    cout << answer << '\n';
}