まず、ペンギンくんが \(N\) 個の仕事全てを行うことができるかを判定します。これは \(S=\{1,2,\ldots,N\}\) なる整数の集合 \(S\) を用意した上で \(x=1,2,\ldots,10^9\) について以下の処理を行い、最終的な \(S\) が空になっているかを調べればよいです。

• \(i \in S\) かつ \(L_i \leq x \leq R_i\) を満たすような \(i\) が存在するなら、その中で \(R_i\) が最小であるもの（複数ある場合はそのいずれか）を選び、\(S\) から削除する。

ペンギンくんが \(N\) 個の仕事全てを行うことができる場合、彼のかなしさは「一日に複数の仕事を行うことができる」と仮定した場合の答え \(ans'\) を用いて、\(\max(ans',1)\) と表されることが分かります。ペンギンくんのかなしさを直接求めることよりも \(ans'\) を求めることの方が遥かに簡単であるため、以降の解説では \(ans'\) を求めに行きます。

さて、\(ans'\) を求める上では、二分探索が有効です。そのため、「\(ans'\) が \(border\) 以下になりうるか？」という部分問題を解くことを考えます。

結論から言うと、上記の部分問題は以下のようなアルゴリズムで解くことが可能です。

• \(x=\min(R)\) なる変数 \(x\), および \(S=\{1,2,\ldots,N\}\) なる整数の集合 \(S\) を用意し、以下の処理を繰り返す。
  • \(i \in S\) かつ \(L_i \leq x \leq R_i\) を満たすような \(i\) が存在しないなら、処理を終える。そうでないなら、そのような \(i\) のうち \(R_i\) が最小であるもの（複数ある場合はそのいずれか）を選び、\(S\) から削除する。その後、削除した要素を \(j\) として \(x\) を \(\min(x+border,R_j)\) で置き換える（これは \(j\) 番目の仕事を \(\min(x+border,R_j)\) 日目に行うことと対応する）。 最終的な \(S\) が空であるなら部分問題の答えは Yes である。

このアルゴリズムの正当性は、

• \(i \in S\) かつ \(L_i \leq x \leq R_i\) を満たすような \(i\) のうち、\(R_i\) が最小でないものに対して操作を行った場合
• \(j\) 番目の仕事を \(\min(x+border,R_j)\) 日目以外に行った場合

それぞれにおいて必ず得をしないことから示すことが可能です。

部分問題を解くアルゴリズムは工夫により \(O(N \log N)\) に高速化できるため、合計での計算量は \(O(N \log N \log (\max(R)))\) となります。

よってこの問題を解くことができました。

実装例 (C++)