No.728 ギブ and テイク

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 27
作問者 : koprickykopricky / テスター : PachicobuePachicobue
3 ProblemId : 1937 / 出題時の順位表

問題文

数直線上に家が $N$ 軒あります。 $i$ 番目の家の座標は $A_i$ とし、それぞれの家には子供が 2 人いるとします。
家 $i$ の子供は一方が数直線上を負の方向に $L_i$ 、もう一方が正の方向に $R_i$ 進み途中で通った家にお菓子を配っていきます。
但し、各 $i$ について座標 $A_i - L_i$ もしくは $A_i + R_i$ に家が存在した場合、家 $i$ の子供はその家を通ったと考えます。
つまり、家 $i$ の子供は $[A_i-L_i, A_i+R_i]$ に存在する家にお菓子を渡します。
このとき家 $i$ が家 $j$ の子供からお菓子をもらい、かつ家 $j$ が家 $i$ の子供からお菓子をもらうようなペア( $i$ , $j$ ) ( $i < j$ )は何組存在しますか?
但し、それぞれの家の子供たちはお菓子を十分多く持っているとします。

(参考) C++, PyPy3(1823ms) で AC できることを確認しています.

入力

$N$
$A_1 \ A_2 \cdots A_N$
$L_1 \ R_1$
$L_2 \ R_2$
$\vdots$
$L_N \ R_N$

$N$ , $A_i$ , $L_i$ , $R_i$ は整数で以下を満たす。
$2 \le N \le 3 \times 10^5$
$0 \le A_1 < A_2 < \cdots < A_N \le 10^9$
$0 \le L_i,R_i \le 10^9$

出力

家 $i$ が家 $j$ の子供からお菓子をもらい、かつ家 $j$ が家 $i$ の子供からお菓子をもらうような $(i,j)\in \{1,2,\dots,N\}^2, i < j$ の個数を出力してください。
答えは32bit整数型に収まらない可能性があることに注意してください。
最後に改行してください。

サンプル

サンプル1
入力
4
1 2 4 7
3 5
0 3
3 4
2 2
出力
2

( $i$ , $j$ ) は (1, 3), (2, 3)の2組存在する。

サンプル2
入力
2
0 3
1 2
5 4
出力
0

そのような( $i$ , $j$ )の組は存在しない。

サンプル3
入力
6
1 2 3 4 5 9
1 10
7 3
5 6
3 4
3 9
3 0
出力
9

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。