問題一覧 > 通常問題

No.1919 Many Monster Battles

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 22
作問者 : とりゐとりゐ / テスター : rianoriano ShirotsumeShirotsume
3 ProblemId : 7994 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-25 23:35:44

問題文

$N\times N$ のマス目があり，Alice と Bob はそれぞれのマスにモンスターを一匹ずつ飼っています．マス $(i,j)$ にいる Alice のモンスターの能力値 $A_{i,j}$ は $|a_i-a_j|$，Bob のモンスターの能力値 $B_{i,j}$ は $|b_i-b_j|$ です．

$N^2$ 個あるそれぞれのマスにおいてバトルが行われ，マス $(i,j)$ のバトルの結果は以下のようになりました．

  • $A_{i,j}\gt B_{i,j}$ のとき，マス $(i,j)$ にいる Bob のモンスターは消滅する．
  • $A_{i,j}= B_{i,j}$ のとき，マス $(i,j)$ にいる Alice, Bob 両者のモンスターはともに消滅する．
  • $A_{i,j}\lt B_{i,j}$ のとき，マス $(i,j)$ にいる Alice のモンスターは消滅する．
バトル後に消滅せずにマス目に残った Alice, Bob のモンスターの能力値の総和を $10^9+7$ で割った余りをそれぞれ求めてください．

入力

$N$
$a_1$ $a_2$ $\ldots$ $a_N$
$b_1$ $b_2$ $\ldots$ $b_N$

  • $2\leq N\leq 2\times 10^5$
  • $1\leq a_i,b_i\leq 10^9$
  • 入力は全て整数である．

出力

バトル後に残った Alice, Bob それぞれのモンスターの能力値の総和を $10^9+7$ で割った余りを順に出力してください．

サンプル

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

バトル前のそれぞれのマス目にいるモンスターの能力値は以下のようになります（左側が Alice のモンスターの能力値，右側が Bob のモンスターの能力値を表しています）． 

0 3 4    0 3 1
3 0 1    3 0 2
4 1 0    1 2 0
バトル後のそれぞれのマス目にいるモンスターの能力値は以下のようになります（消滅したモンスターは - で表されています）． 
- - 4    - - -
- - -    - - 2
4 - -    - 2 -
したがって，バトル後に残った Alice のモンスターの能力値の総和は $8$，Bob のモンスターの能力値の総和は $4$ です．

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

すべてのモンスターが消滅します．

サンプル3
入力
5
700000000 200000000 800000000 600000000 100000000
700000000 800000000 100000000 300000000 900000000
出力
199999986 199999951

$10^9+7$ で割った余りを出力してください．

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