P11021 「LAOI-6」Speed Measurement Between Checkpoints

Little A is driving on a straight highway (can make U-turns instantly, ignoring time and distance), abstracted as a number line. You are given information from $n$ surveillance records. The $i$-th record indicates Little A was at coordinate $x_i$ at time $t_i$. There are $m$ queries. The $i$-th query provides $u_i$ and $v_i$: if the time of the $u_i$-th record is temporarily changed to $v_i$, what is the minimal possible value of the maximum speed (floor to integer) in any valid driving path? **Queries are independent; modifications are reverted after each query.** ### Formal Description Given $n$, $m$, arrays $x$, and $t$ of length $n$. For each of $m$ independent modifications (changing $t_{u_i}$ to $v_i$), compute: $$\left\lfloor \max_{1 \le i < j \le n} \frac{|x_i - x_j|}{|t_i - t_j|} \right\rfloor$$

First line: Two integers $n$, $m$. Next $n$ lines: Two integers $x_i$, $t_i$. Next $m$ lines: Two integers $u_i$, $v_i$.

For each query, output the floor of the maximum speed.

### Sample Explanation After the first query: - Little A's positions: $(-5, 0)$, $(-10, 1)$, $(10, 2)$, $(0, 5)$, $(10, 7)$. - The minimal maximum speed is $20$ (from $t=1$ to $t=2$, moving $-10$ to $10$). --- **Constraints:** - $2 \leq n \leq 10^5$, $1 \leq m \leq 10^5$. - $-10^9 \leq x_i \leq 10^9$, $0 \leq t_i, v_i \leq 10^9$. - $1 \leq u_i \leq n$. - **All $t_i$ (after modifications) are distinct.** ### Test Cases | Test Case | Special Properties | | :-------: | :----------------: | | 1~3 | $n, m \leq 10^3$ | | 4~5 | $-10^5 \leq x_i \leq 10^5$ | | 6~7 | $m \leq 100$ | | 8~10 | None |