提案者です．計算量の悪い別解を紹介します．(最初これで考えていましたが，公式解説のスライドではより計算量の良いものが使われていました．)

答えを二分探索することを考えます．すると部分問題は以下のようなものになります．

縦長の長方形が $N$ 個与えられる．これらが連結であるか判定せよ．

左から $i$ 列目までに限定したときの連結関係を保持しながら $i \rightarrow i + 1$ と更新することを考えます．$i + 1$ 列目の中に限定したときに連結な区間を上から見ていき，$i$ 列目の区間のうち上から $[l, r]$ 番目と連結できる (これは lower_bound, upper_bound などが活用できます) という情報を持って union_find で処理すると良いです．

結局二分探索の部分問題は $O(N \log N)$ などで解けます．答えは $-1$ でないなら高々 $H$ なので，全体では $O(N \log N \log H)$ です．

類題 (ABC)