東京大学プログラミングコンテスト2014

J - 看板の塗り替え


Time limit時間制限 : 5sec / Memory limitメモリ制限 : 256MB

問題

背景

イクタ君は一列に並んだ看板の色がすべて同じ色になるように塗り替えようとしている。 一方、ビッグブリッジ伯爵はイクタ君の邪魔をするために、次々と看板を増やしたり減らしたりする。 それぞれの邪魔が行われた時点で塗り替えを始めると、すべての看板を同じ色にするのにどれだけ時間がかかるか求めよ。

課題

N(1 ≤ N ≤ 100,000) 個の看板が x 軸上に並んでいる。 i 番目の看板は x_i(-10^9 ≤ x_i ≤ 10^9) の位置にあり、a_i(1 ≤ a_i ≤ 200,000) の色で塗られている。 ビッグブリッジ伯爵は Q(1 ≤ Q ≤ 100,000) 回の看板の追加や削除を行う。 各追加と削除が行われた後にイクタ君が塗り替えを始めると、すべての看板を同じ色に塗り替えるのにどれだけ時間がかかるか求めよ。 イクタ君は最初 x = 0 の位置におり、x_p から x_q に移動するのには |x_p - x_q| の時間がかかる。 また、a_p の色の看板を a_q の色に塗り替えるのには |a_p - a_q| の時間がかかる。

配点

300

入力

入力は以下の形式で与えられる。

N
x_1 a_1
:
x_N a_N
Q
c_1 y_1 b_1
:
c_Q y_Q b_Q

1 行目には、はじめから並んでいる看板の数を表す整数 N が与えられる。 続く N 行には、はじめから並んでいる看板の位置と色を表す整数 x_ia_i が与えられる。 N+2 行目には、看板の追加・削除の回数を表す整数 Q が与えられる。 続く Q 行には、看板の追加・削除を表す整数 c_iy_ib_i が与えられる。 c_i はクエリの種類を表す。 c_i = 1 のとき看板の追加を意味し、y_i の位置に b_i の色の看板が追加される。 c_i = 2 のとき看板の削除を意味し、y_i の位置にある b_i の色の看板が削除される。

制約

部分点

この問題には部分点が設定されている。この問題のテストケースのうち 30 点分は追加で以下の制約を満たす。

出力

各追加と削除が行われた後の看板の列に対して、イクタ君がすべての看板を同じ色に塗り替えるのに必要な最小の時間を 1 行づつ出力せよ。


入力例1

1
10 1
3
1 2 2
1 -2 3
2 10 1

出力例1

3
9
3

1 つめのクエリで看板が追加された時点では、位置 x=2 に色 a=2 の看板が、位置 x=10 に色 a=1 の看板があるので、 x=2 の看板を色 a=1 で塗り替えると時間 3 ですべての看板が同じ色になる。

2 つめのクエリで看板が追加された時点では、位置 x=-2 に色 a=3 の看板が、位置 x=2 に色 a=2 の看板が、位置 x=10 に色 a=1 の看板があるので、 x=-2 の看板を色 a=1 で塗り替えたあと、x=2 の看板を色 a=1 で塗り替えると時間 9 ですべての看板が同じ色になる。

3 つめのクエリで看板が削除された時点では、位置 x=-2 に色 a=3 の看板が、位置 x=2 に色 a=2 の看板があるので、どちらかの看板をもう一方の看板の色に塗り替えると時間 3 ですべての看板が同じ色になる。


Submit提出する