問題一覧 > 通常問題

No.728 ギブ and テイク

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 57
作問者 : koprickykopricky / テスター : PachicobuePachicobue
2 ProblemId : 1937 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-08-24 10:01:50

問題文

数直線上に家が $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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。