You are given n points on the straight line — the positions (x-coordinates) of the…
- User
You are given n points on the straight line — the positions (x-coordinates) of the cities and m points on the same line — the positions (x-coordinates) of the cellular towers. All towers work in the same way — they provide cellular network for all cities, which are located at the distance which is no more than r from this tower.
Your task is to find minimal r that each city has been provided by cellular network, i.e. for each city there is at least one cellular tower at the distance which is no more than r.
If r = 0 then a tower provides cellular network only for the point where it is located. One tower can provide cellular network for any number of cities, but all these cities must be at the distance which is no more than r from this tower. Input
The first line contains two positive integers n and m (1 ≤ n, m ≤ 105) — the number of cities and the number of cellular towers.
The second line contains a sequence of n integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the coordinates of cities. It is allowed that there are any number of cities in the same point. All coordinates ai are given in non-decreasing order.
The third line contains a sequence of m integers b1, b2, ..., bm ( - 109 ≤ bj ≤ 109) — the coordinates of cellular towers. It is allowed that there are any number of towers in the same point. All coordinates bj are given in non-decreasing order.
Output
Print minimal r so that each city will be covered by cellular network.
Examples
Input
3 2 -2 2 4 -3 0
Output
4
Input
5 3 1 5 10 14 17 4 11 15
Output
3
Assistant
We need to solve the problem: Given sorted arrays a (cities) of size n, and b (towers) of size m. For each city, we need to have at least one tower within distance r. We need the minimal r such that all cities are covered. This is essentially: min r such that for every city coordinate a_i, there exists tower b_j with |a_i - b_j| <= r.
Since both arrays are sorted, we can perform a two-pointer greedy: For each city, move the tower pointer to the nearest tower >= city or less than city? Actually we need to compute the minimum distance from each city to any tower. Then answer is max over cities of that minimum distance. So we can compute for each city the nearest tower. Since both are sorted, we can do: two pointers: i for cities, j for towers (starting at 0). For each city a_i, advance j while b[j+1] <= a_i (or while the next tower is closer? Actually we want to find the tower with minimum distance. Since towers are sorted, the nearest tower for a_i will be either the closest tower to the left (b_j <= a_i) or the closest to the right (b_{j+1} >= a_i). We can maintain j such that b_j <= a_i < b_{j+1} (or j is last if a_i >= all). Then distance = min(a_i - b_j, b_{j+1} - a_i) with careful handling of boundaries. As we iterate cities in increasing order, we can increase j accordingly. So algorithm:
Initialize j = 0, ans = 0. For each city x in a: while j+1 < m and b[j+1] <= x: j = j+1 // Now b[j] is the last tower <= x, if any; if j==0 and b[0] > x then no tower <= x. Compute d = INF if j < m and b[j] <= x: d = x - b[j] if j+1 < m and b[j+1] > x: d = min(d, b[j+1] - x) // Also if j points to a tower > x? Actually while condition ensures b[j] <= x or j=0 and b[0] > x. If b[0] > x, then j stays 0 but b[0] > x, so no tower <= x. In that case we only consider next tower b[0] - x. But we need to handle j appropriately: after while, we have j such that b[j] <= x (if any) and either j+1 == m or b[j+1] > x. However if b[0] > x, then while condition doesn't increment j because j+1< m and b[j+1] > x? Actually j initially 0. While j+1 < m and b[j+1] <= x: increment j. Since b[1] maybe <= x? But if b[0] > x, then b[1] is >= b[0] > x, so condition fails, j stays 0. But then b[0] > x, so we have no left tower. So we need to treat that case.
So compute d = min distance: d = INF if j < m and b[j] <= x: d = x - b[j] if j+1 < m: d = min(d, b[j+1] - x) // Note: b[j+1] may be <= x? Actually after while, we have b[j+1] > x or j+1 == m. If b[j+1] > x, then it's valid. But if b[j+1] <= x? That would mean we didn't advance enough. However while ensures we advance as long as b[j+1] <= x, so after loop, either j+1 == m or b[j+1] > x. So safe. Also consider the case j == m? Not possible because j only increments up to m-1. If j = m-1 after loop, then no j+1. So only left tower. Also if b[j] > x (possible when b[0] > x) then the first condition false; second condition gives b[1] - x if exists else INF. But also maybe j=0, but b[0] > x so we cannot use b[0] as left. However maybe j-1? Actually we could also consider b[0] as the right tower because it's > x, so distance = b[0] - x. In the above, if j=0 and b[0] > x, then b[0] is actually the right tower. But our second condition uses b[j+1] - x, not b[j] - x. That would use b[1] if exists. So we miss b[0]. So we need to also consider the case where no left tower, i.e., b[j] > x, then the nearest tower is b[j] (the first tower > x). But after while, j is such that b[j] is the largest <= x? Actually the while condition increments j while b[j+1] <= x. This ensures that after loop, either j is index of the last tower <= x, or j is 0 and b[0] > x? Let's test:Suppose towers: [10,20], cities: 5. Initially j=0. While j+1 < m (1<2) and b[1] <=5? b[1]=20 >5, false. So j stays 0. Now b[0]=10 >5, so b[0] is not <=5. So we have no left tower. So j should represent the index of the tower that is <= x only if one exists. In this case we need to treat j as the candidate for right tower? Actually we need to consider the nearest tower to 5: it's 10. That's b[0]. So we need to include b[0] as right tower. But our current method using b[j] as left fails. So we should modify: after the while loop, we might have b[j] > x, meaning no tower <= x. In that case, the nearest tower is b[j] (since b[j] is the smallest tower, as towers are sorted and j is 0 because we never moved). Actually if b[0] > x, then indeed b[0] is the nearest. Similarly, if j is m-1 and b[j] <= x, but j+1 doesn't exist, nearest is left tower. So we need to compute distance as: if m == 0? Not allowed? m >=1. d = INF // find the tower that is just greater or equal to x via binary search? But we can compute by checking: d = abs(x - b[j]) // since j is either last <= or first >? Actually j may be either. But is j always the best candidate? Let's analyze the loop: We increment j while b[j+1] <= x. This means after loop, either j+1 == m or b[j+1] > x. However, we haven't enforced that b[j] <= x. So if b[0] > x, then j=0, and b[0] > x. In that case, b[0] is > x, and b[1]? if exists? b[1] > b[0] > x, so b[0] is the smallest tower. The nearest tower is b[0]. So distance = b[0] - x. So we can take d = abs(x - b[j]) as candidate. But also we should consider b[j-1] if j>0? If b[j] > x and j>0, could b[j-1] be <= x? If j>0 and b[j] > x, but we had while loop that moved j only when b[j+1] <= x, if j>0, then b[j] might be > x but b[j-1] <= x? Let's test: Suppose towers [1,10], cities: 5. Initially j=0. While j+1 < 2 and b[1] <=5? 10 <=5 false, so j stays 0. b[0]=1 <=5, so b[0] is left. But j=0, b[0] <= x. So this case is fine. So scenario where b[j] > x and j>0 can only happen if b[0] > x? Because if there exists a tower <= x, the while loop would have advanced j to at least the last tower <= x. Actually start j=0. While condition uses b[j+1] <= x. Suppose towers: [3,4,10], city: 5. Initially j=0. Check b[1]=4 <=5: true, increment j to 1. Now j=1. Check b[2]=10 <=5? false. Stop. b[1]=4 <=5, good. So j ends at last index with value <= x. So if b[0] > x, then there is no tower <= x, and j=0. So j is the first tower > x. So we can handle by: d = min( (if j < m) abs(x - b[j]), (if j+1 < m) abs(x - b[j+1]) ) But also maybe j-1 could be candidate? If j > 0, then b[j-1] <= x? Actually if j>0, then either b[j] <= x or b[j] > x. But if b[j] > x and j>0, then b[j-1] might be <= x. Could that happen? As argued, because while loop only increments when b[j+1] <= x, if j>0, that means at some point we incremented j from a previous index. That previous index had b[prev] <= x? Let's imagine scenario: towers: [2,5,7], city: 4. Start j=0. Check b[1]=5 <=4? false. So j stays 0. b[0]=2 <=4, so b[0] <= x. So j ends at 0, which is left tower. So j>0 and b[j] > x cannot happen because the while loop would have increased j only if b[j+1] <= x. If we ever increased j to some index k, that means we had b[k] <= x at the moment? Actually when we increment j from j to j+1, we are moving to a tower that is b[j+1] which is <= x. So after increment, the new j points to a tower that is <= x. So j always points to a tower <= x unless there is none and we never moved, in which case j=0 and b[0] > x. So j>0 implies b[j] <= x. So indeed we can rely that if j>0, b[j] <= x; if j==0, we need to check if b[0] <= x or not. But we can just compute distance as: d = INF if j < m: d = abs(x - b[j]) // this covers b[j] being either left or right if j+1 < m: d = min(d, abs(x - b[j+1])) This works because if b[j] <= x, then b[j+1] > x (or doesn't exist). So abs(x-b[j]) = x-b[j]; abs(x-b[j+1]) = b[j+1]-x. If b[j] > x (which only happens when j=0 and b[0] > x), then b[0] is > x, and b[1] if exists > b[0] > x, so abs(x-b[0]) = b[0]-x; abs(x-b[1]) = b[1]-x which is larger. So min is b[0]-x correct. Also if j is last index (j=m-1) and b[j] <= x, then j+1 out of range, only b[j] considered: distance = x - b[j]. That's correct because all towers are left of city. So this simple method works. We just need to make sure j is such that after while loop, j is the largest index with b[j] <= x if exists; else j=0. But we also need to handle the case where we might overshoot? Our while loop increments while b[j+1] <= x. This ensures j is the last index with b[j] <= x if any; if none, j remains 0 and b[0] > x. However, if there is no tower <= x, is it always j=0? Yes because we start at 0 and never increment because condition fails (b[1] > x or no j+1). So j remains 0. That's fine.
So algorithm:
Initialize j = 0, ans = 0. For i from 0 to n-1: x = a[i] while j+1 < m and b[j+1] <= x: j += 1 d = abs(x - b[j]) if j+1 < m: d = min(d, abs(x - b[j+1])) ans = max(ans, d)
But careful: If we have multiple cities, we need to ensure that j is non-decreasing. This loop updates j as cities increase. Since a is non-decreasing, we maintain j accordingly. This works.
Complexities: O(n+m). n,m up to 1e5, fine.
Edge cases: if m=1, then j always 0, while condition fails, d = abs(x - b[0]). ans = max of distances. Works.
Check example:
n=3, m=2: a=[-2,2,4], b=[-3,0]. Initialize j=0, ans=0. x=-2: while j+1<2 and b[1]=0 <= -2? false. d = abs(-2 - (-3)) = 1; j+1<2 so min(1, abs(-2-0)=2) => d=1; ans=1. x=2: while j+1<2 and b[1]=0 <=2? true => j=1. Now while condition: j+1=2 not <2, stop. d = abs(2 - b[1]=0)=2; j+1 not <2, so d=2; ans=max(1,2)=2. x=4: while j+1<2? false. d = abs(4-0)=4; ans= max(2,4)=4. Output 4. matches.
Second example: n=5, a=[1,5,10,14,17]; b=[4,11,15]. j=0, ans=0. x=1: while j+1<3 and b[1]=11 <=1? false. d = abs(1-4)=3; j+1<3 so min(3,abs(1-11)=10)=3; ans=3. x=5: while j+1<3 and b[1]=11 <=5? false. d = abs(5-4)=1; min(1,abs(5-11)=6)=1; ans=3. x=10: while j+1<3 and b[1]=11 <=10? false. d = abs(10-4)=6; min(6,abs(10-11)=1)=1; ans=3. (But note j is still 0; perhaps we need to update j? Actually b[0]=4 <=10, so j should be the last <=10, which is index 0 because b[1]=11 >10. So j=0 is correct. d=1) x=14: while j+1<3 and b[1]=11 <=14? true => j=1. Now while j+1<3 and b[2]=15 <=14? false. d = abs(14-11)=3; j+1<3 so min(3,abs(14-15)=1)=1; ans=3. x=17: while j+1<3 and b[2]=15 <=17? true => j=2. Now j+1 not exist. d = abs(17-15)=2; ans= max(3,2)=3. So answer 3. matches.
Thus correct.
But we must be careful about integer overflow: coordinates up to 1e9, differences up to 2e9, fits in 32-bit signed? Actually 2e9 fits within 32-bit signed int? 2,147,483,647 is max, so 2e9 is fine. Use long long to be safe.
Implementation steps:
- Read n,m.
- Read vector a (n) and b (m).
- Use two-pointer as described.
- Output ans.
But note: The problem statement says the coordinates are given in non-decreasing order, not necessarily strictly increasing. So duplicates allowed. Our algorithm handles duplicates because while loop condition b[j+1] <= x will advance j through duplicate towers as needed.
Time O(n+m), memory O(n+m) but we can just store vectors.
Now also consider that we can binary search for r and check coverage, but the two-pointer greedy directly yields the answer as the maximum of minimum distances, which is minimal r.
But the problem might be intended for binary search? The greedy is simpler. However, we need to ensure correctness: The minimal r needed is exactly the maximum over cities of distance to nearest tower. Because coverage condition: For each city, there must be at least one tower within r. So r must be at least min distance of each city. And if we set r = max_i (min distance to any tower), then each city has a tower within that r. So indeed r* = max_i d_i. So we just need to compute d_i.
Thus solution is straightforward.
We must be mindful of large input and output. Use scanf/printf or fast I/O in C++. Use long long.
Now consider constraints: up to 1e5, O(n+m) works.
Thus implement.
Let's write the code.
Pseudo:
#include <bits/stdc++.h> using namespace std; typedef long long ll;
int main() { int n, m; scanf("%d %d", &n, &m); vector a(n), b(m); for(int i=0;i<n;++i) scanf("%lld", &a[i]); for(int i=0;i<m;++i) scanf("%lld", &b[i]); int j = 0; ll ans = 0; for(int i=0;i<n;++i) { ll x = a[i]; while (j+1 < m && b[j+1] <= x) { j++; } ll d = abs(x - b[j]); if (j+1 < m) { d = min(d, abs(x - b[j+1])); } ans = max(ans, d); } printf("%lld\n", ans); return 0; }
Edge Cases:
- If m == 0? Not possible per constraints m>=1.
- If n == 0? Not possible? n>=1.
- Coordinates negative, but abs works.
Test with some custom:
- n=1,m=1: a=[0], b=[0] => d=0 ans=0.
- n=1,m=1: a=[10], b=[0] => while: j+1? no, d=10 ans=10.
- n=2,m=2: a=[1,100], b=[0,101] => x=1: j stays 0? b[1]=101>1, d=min(abs1-0=1,abs1-101=100)=1 ans=1. x=100: while j+1<2 and b[1]=101 <=100? false. j=0 still. d=min(100-0=100,101-100=1)=1 ans= max(1,1)=1. So r=1. Indeed city 1 covered by 0 (dist1) or 101 (dist100) => nearest 1; city 100 covered by 101 (dist1) => r=1. Good.
- duplicates: a=[5,5,5], b=[5,5] => x=5: while j+1<2 and b[1]=5<=5 true => j=1 (since b[1]<=5, increment j to 1). Then while j+1<2? j+1=2 not <2. d = abs(5-5)=0; j+1 not exist, so d=0 ans=0. Good.
But note: after first city, j=1; second city: x=5, while j+1 <2? false (j+1=2), so j stays 1. d=0. ok.
- scenario: b=[2,4], a=[3] => j=0 initially; while j+1<2 and b[1]=4<=3? false => j=0. d = min(abs3-2=1, abs3-4=1)=1. Good.
Thus algorithm works.
Now just produce final answer.
But I should also note that we could use lower_bound to find nearest tower for each city using binary search, which would be O(n log m). But two-pointer O(n+m) is efficient.
Given n,m up to 1e5, both fine. But O(n log m) also passes. Still O(n+m) better.
Now ensure we used long long.
Now double-check the while condition: while (j+1 < m && b[j+1] <= x) j++. This ensures j is the last index with b[j] <= x. But if there are multiple towers equal to x, we will move j to the last such tower, because b[j+1] <= x will include equal towers. That's fine.
Now what about the possibility that j becomes > m-1? No, because condition j+1 < m ensures j+1 is valid, after increment j becomes j+1, still < m.
Now after while, j could be m-1 (last tower). Then j+1 out of range. We use condition if(j+1 < m) to consider b[j+1].
Now ans is the maximum d.
Thus output ans.
Now re-read problem statement: "One tower can provide cellular network for any number of cities, but all these cities must be at the distance which is no more than r from this tower." This matches the condition.
Edge case: r may be 0 if all cities coincide with a tower.
So final answer.
Now there's a nuance: The input coordinates are given as integers, but answer is integer? Actually distances are integer differences? Since coordinates are integers, distances are integer differences. But could r be half? No, because we require distance <= r, and we want minimal r, if distances are integer, minimal r is integer? Suppose a city at 1, towers at 0 and 3. Minimum distance is 1 (to 0). So integer. For any set of integer positions, nearest tower distance is integer, so max over them is integer. So answer integer.
Thus we output integer.
Now test with some random small case to be safe.
We'll generate small arrays manually.
Write a quick mental test:
n=2,m=3: a=[0,10], b=[-5,5,20] x=0: while j+1<3 and b[1]=5<=0? false, j=0. d=min(|0-(-5)|=5, |0-5|=5) =>5. x=10: while j+1<3 and b[1]=5<=10? true => j=1; while j+1<3 and b[2]=20<=10? false. d=min(|10-5|=5,|10-20|=10)=5. ans=5.
But actual nearest distances: city0 nearest to 5? distance 5, city10 nearest to 5? distance 5, so r=5. Good.
Another: a=[1,2,3], b=[2] => x=1: j=0, while fails; d=|1-2|=1; ans=1. x=2: while? j+1<1? false; d=|2-2|=0; ans=1. x=3: d=|3-2|=1; ans=1. So r=1. But is city1 covered? distance 1 to tower at 2, yes. So r=1 minimal. Good.
Now what if city is far away from all towers: a=[100], b=[0] => d=100 => r=100.
All good.
Thus answer.
Now to produce final response: Provide explanation and code.
Will output the code in C++.
Now note: In problem examples, they used input with negative numbers, but our code works.
Now consider potential bug: When b[j] <= x and b[j+1] also <= x? This can't happen because we moved j to the last such that b[j] <= x and b[j+1] > x or out-of-range. So no.
Now check large values: Use long long to avoid overflow in abs. In C++ abs for long long is llabs? Actually std::abs works for long long in C++11? It should, but to be safe, use llabs or just compute with ternary: d = (x - b[j] > 0 ? x - b[j] : b[j] - x). But using abs from cstdlib might be for int. Better use std::abs with cmath? In practice with <bits/stdc++.h>, std::abs is overloaded for long long? It should. But to be safe, we can write: d = llabs(x - b[j]); and similarly. Use llabs from . Or just compute manually: d = (x > b[j]) ? x - b[j] : b[j] - x; This avoids any function. Let's just use llabs with #include ? Actually we can use abs from ? I'd better use manual.
But simpler: use 0LL + ... Actually we can use abs in C++ with long long; since -std=c++11 it's fine. I'll use abs.
Ok.
Now final answer: Write a clear solution.
Will also mention the reasoning in explanation.
Let's produce final response: explanation and code. ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll;
int main() { int n, m; scanf("%d %d", &n, &m);
vector<ll> cities(n), towers(m); for (int i = 0; i < n; ++i) scanf("%lld", &cities[i]); for (int i = 0; i < m; ++i) scanf("%lld", &towers[i]); int j = 0; // index of the rightmost tower with coordinate <= current city ll ans = 0; for (int i = 0; i < n; ++i) { ll x = cities[i]; // Move j to the last tower that is not greater than x while (j + 1 < m && towers[j + 1] <= x) ++j; // Distance to the tower at position j ll d = llabs(x - towers[j]); // Possibly the next tower (j+1) is closer if (j + 1 < m) d = min(d, llabs(x - towers[j + 1])); ans = max(ans, d); } printf("%lld\n", ans); return 0;}