I tried hard to make it as different from the original problem as possible :). The original problem was from a local olympiad in informatic and it could be restated as follows: "given a directed acyclic graph, we remove each vertex $v$ and check the longest path in such new graph, call it $l(v)$; find $\min l(v)$". Using some transformations ("an excercise for the reader") we find out that we can make it in $O(n+m)$ plus an instance of vertical visibility problem. If we could do this one in $O(n+m)$, then also we would be able to solve the original problem in linear time.

Unforunately, I am looking for an algorithm which is able to work in theoretical $O(n+m)$ time. If I needed only a solution for bounded $n, m$, I would just be happy with $O((n+m)\alpha(n))$ just because $\alpha(n) < 5$ for $n < 2^{2^{2^{65536}}}$ :) You know, it is just a curiosity if it can be always done in linear time.

Of course it is true, C++ standard defines long long int as at least 64-bit integer type. However, won't it be that if $n$ is huge and we denote the word size as $w$ (usually $w=64$), then each find will take $O\left(\frac{n}{w}\right)$ time? Then we would end up with total $O\left(\frac{mn}{w}\right)$.

As I see, assuming you have got 64-bit x86 processor, you are able to handle only $n \le 64$. What if $n$ is in the order of millions?

@invalid_id Could you please elaborate on this method? That is because I have no idea how to "keep track of the overall maximum" efficiently? Sometimes the maximum may decrease in a strange way. Look at $x=2$ and $x=3$ in the example above. Before $x=2$ the heights of the segments were $2, 5$ (max 5); then they were $2, 3, 5$ (max 5), but then 5 disappeared and max was = 3. How would you deal with this?

@invalid_id Yes, I tried. However, in this case the sweep line must react appropriately when it meets the beginning of the segment (in other words, add the number equal to segment's $y$-coordinate to the multiset), meets the end of the segment (remove an occurence of $y$-coordinate) and output the highest active segment (output maximum value in the multiset). I have not heard of any data structures letting us do this in (amortized) constant time.