Editorial

Group 1: $n=m$; $a_i=b_i$ $(1\le i\le n)$;

Let's notice that our equation:

Can be rewritten as:

In other words, it is an identity, so all $x$ satisfy it, therefore it is enough to output the word "Infinity".

Group 2: $n=m=1$

In this group, there are two key cases:

1. When $a_0=b_0$, it is again an identity and the answer is Infinity.

2. Otherwise, we can use the fact that $|a-b|$ shows the distance between points on the number line and the equation $|x-a_0|=|x-b_0|$ simply shows that the distance from point $a_0$ to $x$ and from $b_0$ to $x$ are equal. Such a point is exactly one and it lies exactly in the middle between $a_0$ and $b_0$, indeed, because the midpoint of points lying at equal distances from the given points is the perpendicular bisector of the segment connecting the given points, and since we are solving the problem in real numbers, only one point, which we described above, will suit us.

For all subsequent test groups, we will need a few observations:

1. $|x-a|=x-a$ if $x\ge a$ and $|x-a|=-(x-a)=a-x$ otherwise. In the future, we will call the first situation as "the absolute value opens with a positive sign", and "the second as the absolute value opens with a negative sign".

2. Let's move everything from right to left, now our task is to find the number of zeros in such a function:

   $$f(x)=|x-a_1|+|x-a_2|+|x-a_3|+\dots +|x-a_n|-|x-b_1|-|x-b_2|-|x-b_3|-\dots -|x-b_m|$$

3. In one interval where no absolute value will change its sign, our function will be a straight line. This happens because our expression turns into an expression without absolute values, then we can group $x$ and everything else and get the formula $f(x)=kx+b$ - a straight line.

4. Breakpoints, when the sign of some absolute value (and consequently the function) changes, coincide with an element from the array $a$ or from the array $b$.

5. The maximum number of breakpoints is $n+m$.

6. From the previous fact, it follows that the maximum number of different pieces of straight lines (from which our function consists) is $n+m+2$.

Group 3: $|a_i|\le 20$ $(1\le i\le n)$; $|b_i|\le 20$ $(1\le i\le m)$;

Let's just consider the half-intervals $(-\infty ;-20],(-20;-19],(-19;-18],\dots (19;20],(20,+\infty )$ In each of them, the value of the function is the same because the breakpoint could only be an integer. In each case, we can expand the absolute values, compose a linear function $l(x)$, find such an $x$ that $l(x)=0$, and check if $x$ lies in the given half-interval. Here are 3 remarks worth making:

1. if $l(x)=0$ then "Infinity" can be output.

2. if $l(x)=a,a\ne 0$ then we can simply move on

3. in general, this can also be considered in fractional numbers, but it can be noticed that our $x$ will always be rational numbers, which means they can be represented as a fraction and compared as a fraction (there will be no problems with accuracy)

Group 4: $n,m\le 1000$

It can be easily noticed that when considering an interval of length 1, many functions will have the same formula. Instead, let's consider the half-intervals between two neighboring breakpoints. For this, we will create an array $c$ containing all elements of the array $a$ and the array $b$, sort it and consider such half-intervals:

And on each of them, we will solve it just like in the previous group, the solution for one segment will work in $O(n+m)$, so the total asymptotic will be $O((n+m{)}^2)$

Group 5:

For this group, let's optimize the algorithm for creating a function for one interval. Let's notice that $l(x)=fa(x)-fb(x)$ where

The algorithm for constructing $fa(x)$ will be further discussed, notice that for $fb(x)$ everything is analogous.

The first step is to sort the array $a$.

Let's say we have the half-interval $(c,d)$ then the number of absolute values that opened with a positive sign is the number of such numbers $a_i(1\le i\le n)$ that $a_i\le c$ and with a negative sign, it is all the rest, then the coefficient $k$ in our function is the difference between the first and second number. With the remaining coefficient, everything is slightly more complicated, let's call $h$ such a maximum number that $a_h\le c$ Then, rewriting our expression without the absolute value, we get:

So our task has been reduced to the task of finding the sum on the segment, which can be done using prefix sums.

On one half-interval, we can handle it in $O(log(n+m))$, so the total asymptotic will be $O((n+m)log(n+m))$