Buses

We need answer many queries: starting at position $p$, what is the earliest possible time to reach ell?

The trap is pretending this is just “take the best bus by coordinate.” Nope. Time matters. A bus might be physically useful-looking, but if it already passed, tough luck.

The state key

Suppose at some moment you are at position $p$ at time $T$. Can you catch bus $(s,t)$?

The bus starts at $s$ at time $0$, moves with speed $x$, and stops at $t$. If you meet it at position $q$, then the bus reaches $q$ at time

$\frac{q-s}{x}.$

You can reach $q$ by then iff

$|q-p|\le y\left(\frac{q-s}{x}-T\right).$

For catching a bus that is ahead / to your right, the limiting case is whether you can meet it by the time it reaches its final stop $t$:

$t-p\le y\left(\frac{t-s}{x}-T\right).$

Multiply by $x$:

$x(t-p)\le y(t-s)-xyT.$

Rearrange:

$xp+xyT\ge xt-y(t-s).$

So define:

$Q(p,T)=xp+xyT$

and for each bus:

$A=xt-y(t-s)=(x-y)t+ys.$

Then the bus is catchable exactly when

$Q(p,T)\ge A.$

That is the whole sauce. One threshold. No geometry circus.

For an initial person at position $p$, time is $0$, so their key is simply

$Q=xp.$

What happens after taking a bus?

If you catch bus $i=(s_i,t_i)$, no matter where you boarded it, it reaches $t_i$ at absolute time

$\frac{t_i-s_i}{x}.$

So riding bus $i$ puts you into a new state:

$p=t_i,\qquad T=\frac{t_i-s_i}{x}.$

Its key is

$Q_i=x t_i+xy\cdot\frac{t_i-s_i}{x}=x t_i+y(t_i-s_i).$

From there, either walk to the end, or catch another bus whose $A$ threshold is at most this $Q_i$.

Let $dp_i$ be the minimum final arrival time if you have caught bus $i$ and ride it to its endpoint. Then:

$dp_i=\min\left(\frac{t_i-s_i}{x}+\frac{\ell-t_i}{y},\ \min_{j:A_j\le Q_i} dp_j\right).$

The first term means: ride this bus, then walk. The second term means: ride this bus, then transfer to some other useful bus.

Why processing order works

For a bus $i$:

$Q_i=x t_i+y(t_i-s_i),$

while its own catch threshold is

$A_i=x t_i-y(t_i-s_i).$

So

$Q_i-A_i=2y(t_i-s_i)>0.$

Taking buses moves you to a strictly “larger” key. Therefore, if we process buses in decreasing $Q_i$, all buses you could transfer to from the current endpoint are already available in the data structure.

This is the greedy/sorting part. The sorting is doing real work, not just looking pretty for the compiler.

Data structure

Each computed bus contributes:

• key threshold $A_i$
• value $dp_i$

For a query key $Q$, we need:

$\min dp_i\quad\text{over all }A_i\le Q.$

That is a prefix minimum query. Coordinate-compress all $A_i$ values and use a Fenwick tree storing minimums.

For each bus in decreasing $Q_i$:

1. Query the Fenwick tree for all $A\le Q_i$.
2. Compare that with walking after this bus stops.
3. Insert this bus’s $dp_i$ at coordinate $A_i$.

For each person at position $p$:

$answer=\min\left(\frac{\ell-p}{y},\ \min_{i:A_i\le xp}dp_i\right).$

Walking is always legal, so even if no bus is useful, the answer is fine.

Complexity

Sorting and Fenwick operations give:

$O((n+m)\log n)$

Memory is $O(n)$. Clean enough for $2\cdot 10^5$ without doing anything cursed.