One of the farming chores Farmer John dislikes the most is hauling around lots
of cow manure. In order to streamline this process, he comes up with an
intriguing idea: instead of hauling manure between two points in a cart behind
his tractor, why not shoot it through the air with a giant manure slingshot?
(indeed, what could possibly go wrong...)

Farmer John's farm is built along a single long straight road, so any location
on his farm can be described simply using its position along this road
(effectively a point on the number line). FJ builds \(N\) slingshots
(\(1 \leq N \leq 10^5\)), where the \(i\)th slingshot is described by three integers
\(x_i\), \(y_i\), and \(t_i\), specifying that this slingshot can shoot manure from
position \(x_i\) to position \(y_i\) in only \(t_i\) total units of time.

FJ has \(M\) piles of manure to transport (\(1 \leq M \leq 10^5\)). The \(j\)th such
pile needs to be moved from position \(a_j\) to position \(b_j\). Hauling manure
with the tractor for a distance of \(d\) takes \(d\) units of time. FJ is hoping to
reduce this by allowing up to one use of any slingshot for transporting each
pile of manure. Time FJ spends moving his tractor without manure in it does
not count.

For each of the \(M\) manure piles, please help FJ determine the minimum possible
transportation time, given that FJ can use up to one slingshot during the
process.

Problem credits: Brian Dean

Problem credits: Brian Dean

The first line of input contains \(N\) and \(M\). The next \(N\) lines each describe
a single slingshot in terms of integers \(x_i\), \(y_i\), and \(t_i\)
(\(0 \leq x_i, y_i, t_i \leq 10^9\)). The final \(M\) lines describe piles of manure
that need to be moved, in terms of integers \(a_j\) and \(b_j\).

Print \(M\) lines of output, one for each manure pile, indicating the minimum time
needed to transport it.

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > February > Platinum