Дана координатная плоскость, которая простирается от $$$(0,0)$$$ до $$$(x, y)$$$. Вы находитесь в точке $$$(0,0)$$$ и хотите добраться до $$$(x, y)$$$.
Однако на плоскости расположены $$$n$$$ горизонтальных лазеров, $$$i$$$-й из которых непрерывно светит из $$$(0, a_i)$$$ в $$$(x, a_i)$$$. Кроме того, есть $$$m$$$ вертикальных лазеров, $$$i$$$-й из которых непрерывно светит из $$$(b_i, 0)$$$ в $$$(b_i, y)$$$.
Вы можете двигаться в любом направлении, чтобы достичь точки $$$(x, y)$$$, но ваше движение должно быть непрерывной кривой, которая лежит внутри плоскости. Каждый раз, когда вы пересекаете вертикальный или горизонтальный лазер, это считается одним пересечением. В частности, если вы проходите через точку пересечения двух лазеров, это считается двумя пересечениями.
Например, если $$$x = y = 2$$$, $$$n = m = 1$$$, $$$a = [1]$$$, $$$b = [1]$$$, движение может быть следующим:
Каково минимальное количество пересечений, необходимое для достижения точки $$$(x, y)$$$?
Первая строка содержит $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество независимых наборов входных данных.
Первая строка каждого набора входных данных содержит четыре целых числа $$$n$$$, $$$m$$$, $$$x$$$ и $$$y$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5, 2 \leq x ,y \leq 10^9$$$).
Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \lt a_i \lt y$$$) — координаты по оси y горизонтальных лазеров. Гарантируется, что $$$a_i \gt a_{i-1}$$$ для всех $$$i \gt 1$$$.
Следующая строка содержит $$$m$$$ целых чисел $$$b_1, b_2, \ldots, b_m$$$ ($$$0 \lt b_i \lt x$$$) — координаты по оси x вертикальных лазеров. Гарантируется, что $$$b_i \gt b_{i-1}$$$ для всех $$$i \gt 1$$$.
Гарантируется, что сумма $$$n$$$ и $$$m$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите минимальное количество пересечений, необходимое для достижения точки $$$(x, y)$$$, на новой строке.
21 1 2 2112 1 100000 10000042 5832
2 3
| Codeforces Round 1050 (Div. 4) |
|---|
| Закончено |
