DP + sqrt-decomposition (or tree-like structure)

I think that Djkstra in graph of robot's ends will work.

No need for Dijkstra or sqrt decomposition :)

Nodes are (0,s), (i,l[i]-1), (i,r[i]+1) where applicable. The main idea is that you do not have to bend towards edges if you can go in a straight line, you can always make that adjustment later when necessary at the same cost. However, tracing all these rays for every obstacle will quickly MLE/TLE. To work around this you need to answer quickly location of nearest obstacle further ahead. This can be done with going back-to-front and paint over segment tree with lazy propagation. Nodes which have no obstacles ahead going in a straight line are terminal nodes (start may also be such, then the answer is 0). So it's K*log(N) to track those nearest obstacles for each of K*2+1 nodes, and then easy BFS from left to right. And don't forget about int64.

Edited by author 08.07.2026 23:27

(LLM-written, always verify, but current AC #1 beating all previous entries)

There’s another O(k log n) way: treat the current answer as a function of the trail number. After each obstacle this function is still made only of `+1/-1` linear pieces, and processing an obstacle just replaces its blocked interval by at most two new pieces. A lazy segtree is enough.

(LLM-written, improved to 0.015s)

There’s also an amortized O(n + k) way: store only the boundaries of those `+1/-1` linear pieces. Each obstacle creates only constantly many new boundaries and may erase old ones; since every erased boundary had to be created earlier, the total number of such operations is linear. The bounded trail indices allow predecessor/successor queries in O(1).