\((l,r)\) の組としては \((1,1),(2,2),\ldots,(N,N)\) と \((1,N)\) のみを考えればよいです。

計算量は \(O(N)\) です。

証明の概略です。

\(f(l,r)=(\max_{l \le i \le r} A_i) \times (\min_{l \le i \le r} B_i)\) とします。

1. \(f(l,r)<0\) となる \((l,r)\) が存在する場合

\(\max_{l \le i \le r} A_i>0,\min_{l \le i \le r} B_i<0\) のときは、区間は長いほど得なので、\((l,r)=(1,N)\) のみで十分です。

\(\max_{l \le i \le r} A_i<0,\min_{l \le i \le r} B_i>0\) のときは、区間は短いほど得なので、長さ \(1\) の区間のみで十分です。

2. \(f(l,r)<0\) となる \((l,r)\) が存在しない場合

\(A_i=0\) または \(B_i=0\) となる \(i\) が存在すれば、\(f(i,i)=0\) が最適です。以下、そうでない場合を考えます。

\(\max_{l \le i \le r} A_i>0,\min_{l \le i \le r} B_i>0\) のときは、区間は短いほど得なので、長さ \(1\) の区間のみで十分です。

\(\max_{l \le i \le r} A_i<0,\min_{l \le i \le r} B_i<0\) のときも、区間は短いほど得なので、長さ \(1\) の区間のみで十分です。