すべての を配列 に、すべての を配列 に入れる。各配列の長さは になる。和が等しくても、添字の組ごとに一つの要素として格納する。
両配列を昇順に並べる。 の未処理の最小値 と の未処理の最大値 を見る。 のとき、 と の残りのどの要素を足しても負になるため、 側を進める。 のとき、 と の残りのどの要素を足しても正になるため、 側を進める。
のとき、 と が連続する個数をそれぞれ とする。両方の区間から一つずつ選ぶ 通りを答えに加え、両側で対応する区間を飛ばす。各値と対になるのは符号を反転した値だけなので、同じ添字の組を二度数えることはない。
時間計算量は 、空間計算量は である。四つの入力値の和は 32 ビット符号付き整数に収まる。出現回数の積と答えは最大 なので、64 ビット整数で計算する。
Solution written by GPT