G - プレゼント配り2

Contest Duration: 2019-12-26(Thu) 03:50 - 2019-12-26(Thu) 07:50 (local time) (240 minutes) Back to Home

G - プレゼント配り2 Editorial

Time Limit: 5 sec / Memory Limit: 1024 MB

配点: $100$ 点

問題文

E869120 君は「AtCoder サンタ事務局」の社員であり，サンタにプレゼントを効率的に配らせるための仕事を，毎年行っています．

さて，今年もクリスマスがやってきました．彼の今年の仕事は，「AtCoder 通り」において，サンタと家の位置の情報を仕入れ，サンタのプレゼント配りを効率化することです．

AtCoder 通りは，西から東に走る，長さ $1 \ 000 \ 000 \ 000$ の道路です．最初，E869120 君に入ってきた，家の位置とサンタの位置の情報は，以下のようになります．

その通りに家は $N$ 軒ある．家には $1, 2, ..., N$ と番号づけられており，番号 $i$ の家は，道路の西端から $A_i$ メートルの位置にある．
その通りにサンタは $M$ 人いる．サンタには $1, 2, ..., M$ と番号づけられており，番号 $i$ のサンタは，道路の西端から $B_i$ メートルの位置にいる．

しかし，AtCoder 通りでは，家の引っ越しやサンタの移動などがたびたび起こります．そのため，クリスマスまでに $Q$ 回の情報変更が行われます． $i$ 回目の情報変更について，

$T_i = 1$ のとき：番号 $C_i$ の家の位置が，道路の西端から $D_i$ メートルの位置に変更される．
$T_i = 2$ のとき：番号 $C_i$ のサンタの位置が，道路の西端から $D_i$ メートルの位置に変更される．

そのとき， $i = 0, 1, 2, ..., Q$ について， $i$ 回目の変更直後の情報において，以下の問題に答えてください．

すべての家にプレゼントが配られるために， $M$ 人のサンタを合計して，何メートル移動する必要があるか，求めよ．
ただし，すべてのサンタは常にプレゼントを十分な個数持っているものとする．
また，サンタは家のある位置に移動することによって，プレゼントを配ることができる．遠い位置からプレゼントを投げて配るなどということはできない．サンタ達はプレゼントを配り終わった後，元の場所に戻る必要はない．

ただし，「 $0$ 回目の変更直後の情報」というのは，最初に E869120 君に入ってきた情報のことを指します．

制約

$1 \leq N \leq 100 \ 000$
$1 \leq M \leq 100 \ 000$
$0 \leq Q \leq 100 \ 000$
$0 \leq A_i \leq 1 \ 000 \ 000 \ 000$ , $A_i$ は偶数
$0 \leq B_i \leq 1 \ 000 \ 000 \ 000$ , $B_i$ は奇数
$1 \leq T_i \leq 2$
$T_i = 1$ のとき， $1 \leq C_i \leq N$ ， $0 \leq D_i \leq 1 \ 000 \ 000 \ 000$ を満たし， $D_i$ は偶数である．
$T_i = 2$ のとき， $1 \leq C_i \leq M$ ， $0 \leq D_i \leq 1 \ 000 \ 000 \ 000$ を満たし， $D_i$ は奇数である．
$2$ つの家が同じ位置に来るような情報の変更はない．
$2$ つのサンタが同じ位置に来るような情報の変更はない．

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．

(2 点) $M = 1$ ， $Q = 0$ ．
(6 点) $M = 2$ ， $Q = 0$ ．
(14 点) $N \leq 250$ ， $M \leq 250$ ， $Q = 0$ ．
(9 点) $N \leq 3 \ 000$ ， $M \leq 3 \ 000$ ， $Q = 0$ ．
(9 点) $Q = 0$ ．
(35 点) $N \leq 40 \ 000, M \leq 40 \ 000, Q \leq 40 \ 000, T_i = 1$ ．
(19 点) $N \leq 40 \ 000, M \leq 40 \ 000, Q \leq 40 \ 000$ ．
(6 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられます．

 $N$ 
 $A_1$   $A_2$   $A_3$  ...  $A_N$ 
 $M$ 
 $B_1$   $B_2$   $B_3$  ...  $B_M$ 
 $Q$ 
 $T_1$   $C_1$   $D_1$ 
 $T_2$   $C_2$   $D_2$ 
 $T_3$   $C_3$   $D_3$ 
: : :
 $T_Q$   $C_Q$   $D_Q$

出力

$Q+1$ 行に渡って出力してください．
$i$ 行目には， $i-1$ 番目の変更の直後の情報において，サンタの合計移動距離の最小値を出力してください．

入力例 1Copy

Copy

5
12 18 36 50 68
1
25
0

出力例 1Copy

Copy

以下のようにサンタが移動する場合，合計移動距離 $69$ となり，これが最小です．

サンタ $1$ が家 $1$ に移動し，プレゼントを配る．その時点での移動距離は $13$ である．
サンタ $1$ が家 $2$ に移動し，プレゼントを配る．その時点での移動距離は $19$ である．
サンタ $1$ が家 $3$ に移動し，プレゼントを配る．その時点での移動距離は $37$ である．
サンタ $1$ が家 $4$ に移動し，プレゼントを配る．その時点での移動距離は $51$ である．
サンタ $1$ が家 $5$ に移動し，プレゼントを配る．その時点での移動距離は $69$ である．

入力例 2Copy

Copy

5
138 218 224 110 146
2
127 157
0

出力例 2Copy

Copy

この入力例は小課題2の制約を満たします．
なお，小課題2は，入力例 1 のような $M = 1$ の場合を含まないことにご注意ください．

入力例 3Copy

Copy

10
2412 1276 1948 2000 2542 2558 2070 2712 2820 1542
6
3001 1545 1213 2473 2559 2019
0

出力例 3Copy

Copy

この入力例は小課題 3, 4, 5 の制約を満たします．

入力例 4Copy

Copy

10
2412 1276 1948 2000 2542 2558 2070 2712 2820 1542
6
3001 1545 1213 2473 2559 2019
7
1 2 1348
1 8 3200
2 3 2951
1 4 2102
2 5 1137
1 10 420
2 1 2207

出力例 4Copy

Copy