式の簡略化のため \(L, R, A\) の添え字は \(0\)-indexed とします。 また、\(\displaystyle X \coloneqq \max _ i R _ i\) とおきます。

部分点と満点に共通の考察として、公差 \(d\) を固定して初項 \(A _ 0\) が取り得る値の範囲を考えると以下のような式が得られます。

\[\max _ i (- id + L _ i) \leq A _ 0 \leq \min _ i (- id + R _ i)\]

部分点 (\(X \leq 10 ^ 5\))

\(A _ 0\) が存在し得る公差 \(d\) は \(\displaystyle - \frac{X}{N - 1} \leq d \leq \frac{X}{N - 1}\) を満たします。 それぞれについて \(A _ 0\) の範囲を \(O(N)\) 掛けて調べることで時間計算量 \(O(N + X)\) の解法が得られ、部分点を獲得できます。

満点

\(- id + L _ i\) は \(i\) によって定まる \(d\) についての \(1\) 次式です。 したがって、それらの最大値 \(\displaystyle \max _ i (- id + L _ i)\) は \(d\) についての下に凸な折れ線になります。 この折れ線は Convex Hull Trick などと呼ばれる手法と同様にして \(O(N)\) で計算することができます。 同様に、\(R\) についての条件も上に凸な折れ線となります。

この \(2\) つの折れ線に囲まれた領域の格子点の個数を数えれば良いです。 \(d\) の範囲を適切に \(O(N)\) 個の区間に区切ることでこの領域を台形に分割することができ、格子点の個数はそれぞれ \(O(1)\) で求まります。 時間計算量は \(O(N)\) です。