P1870 Bus

A city has a parking lot that can hold $n$ buses. Each day, these buses leave the depot in order and head to a terminal that is $d$ meters away. The $i$-th bus leaves the parking lot at time $t_i$ seconds, travels with a maximum speed no greater than $v_i$ meters per second, and has a maximum acceleration of $a$. A bus can decelerate instantaneously and can change its acceleration instantaneously. The maximum acceleration is the same for every bus and equals $a$. No matter how powerful a bus is, it may not overtake any other bus. If a bus catches up with another, the rear bus and the front bus travel side by side together and reach the terminal at the same time. Drivers always try to reach the terminal as fast as possible. As the bus company owner, you want every bus to reach the terminal as quickly as possible. It is not required that the bus speed be $0$ upon arrival at the terminal. When a bus leaves the parking lot, its initial speed is $0$. From a physics perspective, treat a bus as an abstract point-like object; apart from being able to accelerate and decelerate, all other effects on speed can be ignored.

The first line contains three space-separated integers $n, a, d$ ($1 \leq n \leq 10^5$, $1 \leq a, d \leq 10^6$), denoting the number of buses, the maximum acceleration, and the distance to the terminal, respectively. The next $n$ lines each contain a pair of integers $t_i, v_i$ ($0 \leq t_1 < t_2 < \cdots < t_{n-1} < t_n \leq 10^6$, $1 \leq v_i \leq 10^6$), denoting the departure time of each bus and its maximum possible speed, respectively.

Output the arrival time at the terminal for each bus. Print one bus’s arrival time per line, in the same order as the input. The relative or absolute error of each answer must not exceed $10^{-4}$ (i.e., keep 4 decimal places at the end).

[Sample explanation] The second bus can catch up with the first bus at a point $510.5$ kilometers from the terminal. Then there are $9489.5$ kilometers remaining, and both buses travel together at $10$ km/h to reach the terminal at time $1000.5$ seconds. The third bus cannot catch up with any other bus, and its arrival time is $11000.05$ seconds. Translated by ChatGPT 5