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.

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;