P6172 [USACO16FEB] Load Balancing P

*This problem has the same meaning as [the Silver problem with the same name](/problem/P3138). The only difference is the Constraints.*

Farmer John has $N$ cows ($1 \leq N \leq 10^5$) scattered across the farm. The farm is an infinitely large 2D plane. The position of the $i$-th cow is $(x_i, y_i)$ (it is guaranteed that both $x_i$ and $y_i$ are positive odd numbers, and $x_i, y_i \leq 10^6$), and no two cows are at the same location. FJ wants to build a vertical fence with equation $x = a$, and also a horizontal fence with equation $y = b$. To prevent the fences from passing through any cows, both $a$ and $b$ must be even numbers. It is easy to see that these two fences intersect at $(a, b)$, dividing the farm into four regions. FJ wants the numbers of cows in the four regions to be as balanced as possible, avoiding the situation where one region has many cows while another has few. Let $M$ be the maximum number of cows among the four regions. Please help FJ find the minimum possible value of $M$.

The first line contains an integer $N$. The next $N$ lines each contain two integers $x_i, y_i$, describing the position of the $i$-th cow.

Output the minimum value of $M$.

Translated by ChatGPT 5