P6281 [USACO20OPEN] Social Distancing S

Due to the outbreak of the highly contagious cow disease COWVID-19, Farmer John is very worried about the health of his cows. To limit the spread of the disease, Farmer John’s $N$ cows ($2\le N\le 10^5$) decide to practice “social distancing” and spread out across the farm. The farm can be seen as a one-dimensional number line with $M$ disjoint intervals ($1\le M\le 10^5$) that contain grass available for grazing. The cows want to stand at different integer positions, where each chosen position has grass, and maximize the value of $D$, where $D$ is the distance between the closest two cows. Please help the cows find the maximum possible value of $D$.

The first line contains $N$ and $M$. The following $M$ lines each contain two integers $a$ and $b$ describing an interval, where $0\le a\le b\le 10^{18}$. No two intervals overlap or touch at endpoints. A cow standing on an endpoint of an interval is considered to be standing on grass.

Output the maximum possible value of $D$ such that the distance between every pair of cows is at least $D$. It is guaranteed that a solution with $D>0$ exists.

### Sample Explanation One way to achieve $D=2$ is to place the cows at positions $0$, $2$, $4$, $6$, and $9$. ### Subtasks - Test cases $2$-$3$ satisfy $b\le 10^5$. - Test cases $4$-$10$ have no additional constraints. Translated by ChatGPT 5