ACPC 2017 - Lane Switching

Time Complexity: $\mathcal{O}(M(\log M+\log R))$

Similar to the previous two problems in this module, we can binary search on the answer. However, there's a bit more implementation involved because we need to construct the graph first. Each vertex in the graph corresponds to a range of unoccupied space in a lane, and we draw an edge between two vertices with weight equal to the length of their vertical intersection.

int N,M,R;
vpi todo[100], range[100];
int ind = 0; 
array<int,3> st; // your car (starting position)

vector<vi> label;
vector<vpi> adj;
vi col;
vb vis;