3 - 通信妨害 (Communication Jamming) Editorial /

Time Limit: 2 sec / Memory Limit: 256 MiB

配点 : 100 点

問題文

JOI 国は平面上に存在する.N 個の村があり,村には 1 から N までの番号がついている.村 i は座標 (i, 0) に存在する点とみなす.現在,JOI 国では村を接続する通信回線を整備しようとしている.障害に備え,通信回線は二系統整備される予定である.これらを系統 1 と系統 2 と呼ぶ.

系統 k には,ハブが M_{k} 個存在し,回線が N + M_{k} - 1 本ある.系統 k のハブには 1 から M_{k} までの番号がついており,ハブ j は座標 (X_{k j}, Y_{k j}) に存在する点とみなす.系統 k の各回線は,村と系統 k のハブ,または系統 k のハブ同士を接続する.各回線は,両端を結ぶ線分とみなす.任意の 2 つの回線は端点同士以外で共有点を持たないようになっていることが保証されている.系統 1 のハブ j の y 座標 Y_{1j} は 0 より大きい.また,系統 2 のハブ j の y 座標 Y_{2j} は 0 より小さい.

ある 2 つの地点が通信できるとは,それらの地点が回線により間接的に接続されていることとする.すなわち,回線に沿った移動を繰り返して,片方の地点からもう片方の地点へ移動できるならば,その 2 つの地点は通信ができる.系統 1 の回線のみを考えても,系統 2 の回線のみを考えても,任意の 2 つの村及びハブは通信可能である.

下図は通信回線の例である.灰色の円は系統 1 のハブ,黒い円は系統 2 のハブ,白い円は村を表す.

図

図 1: 通信回線の例 1

図 2: 通信回線の例 2

計画を検討するにあたって,外部からの攻撃で,どの程度攻撃を受けても通信が可能であるかを調べたい.外部からの攻撃は,2 つの数 A, B (A \geqq 0,B \leqq 0) により表現され,y 座標が A より大きい全てのハブと y 座標が B より小さい全てのハブを破壊するものと想定している.ハブが破壊されると,そこを経由した通信は行えなくなる.

課題

村や各系統の情報が与えられる.また,Q 個のクエリが与えられる.各クエリ q は 1 つの整数 A_{q} で表され,y 座標が A_{q} より大きい全てのハブが破壊される場合を意味する.各クエリに対し,加えて y 座標がいくつ未満のハブまでであれば破壊されても全村間の通信が可能であるかを答えよ.すなわち,整数 B_{q} であって,y 座標が A_{q} より大きい全てのハブと y 座標が B_{q} より小さい全てのハブを破壊しても全村間の通信が可能であるような最大の B_{q} (B_{q} \leqq 0) を答えよ.

入力

標準入力から以下の入力を読み込め.

  • 1 行目には 4 つの整数 N, M_{1}, M_{2}, Q が空白を区切りとして書かれている.
  • 続く M_{1} + (N + M_{1} - 1) 行には,系統 1 の情報が書かれている.

    • 最初の M_{1} 行の i 行目 (1 \leqq i \leqq M_{1}) には,2 つの整数 X_{1i}, Y_{1i} が書かれている.
    • 続く N + M_{1} - 1 行の i 行目 (1 \leqq i \leqq N + M_{1} - 1) には,回線 i の情報を表す 3 つの整数 T_{1i},C_{1i}, D_{1i} が書かれている (T_{1i} = 1, 2).

      • T_{1i} が 1 のとき,回線 i は村 C_{1i} とハブ D_{1i} を接続する (1 \leqq C_{1i} \leqq N かつ 1 \leqq D_{1i} \leqq M_{1}).
      • T_{1i} が 2 のとき,回線 i はハブ C_{1i} とハブ D_{1i} を接続する (1 \leqq C_{1i}, D_{1i} \leqq M_{1} かつ C_{1i} \ne D_{1i}).
  • 続く M_{2} + (N + M_{2} - 1) 行には,系統 2 の情報が書かれている.

    • 最初の M_{2} 行の i 行目 (1 \leqq i \leqq M_{2}) には,2 つの整数 X_{2i}, Y_{2i} が書かれている.
    • 続く N + M_{2} - 1 行の i 行目 (1 \leqq i \leqq N + M_{2} - 1) には,回線 i の情報を表す 3 つの整数 T_{2i},C_{2i}, D_{2i} が書かれている (T_{2i} = 1, 2).

      • T_{2i} が 1 のとき,回線 i は村 C_{2i} とハブ D_{2i} を接続する (1 \leqq C_{2i} \leqq N かつ 1 \leqq D_{2i} \leqq M_{2}).
      • T_{2i} が 2 のとき,回線 i はハブ C_{2i} とハブ D_{2i} を接続する (1 \leqq C_{2i}, D_{2i} \leqq M_{2} かつ C_{2i} \ne D_{2i}).
  • 続く Q 行の i 行目 (1 \leqq i \leqq Q) には 1 つの整数 A_{i} が書かれている.

出力

標準出力に Q 行出力せよ.i 行目 (1 \leqq i \leqq Q) には,クエリ i への答えを表す整数 B_{i} を出力せよ.

答えが 0 の場合,-0 と出力してはならない.

制約

すべての入力データは以下の条件を満たす.

  • 1 \leqq N, M_{1}, M_{2} \leqq 100\,000.
  • -1\,000\,000\,000 \leqq X_{1i} \leqq 1\,000\,000\,000 (1 \leqq i \leqq M_{1}).
  • -1\,000\,000\,000 \leqq X_{2i} \leqq 1\,000\,000\,000 (1 \leqq i \leqq M_{2}).
  • 1 \leqq Y_{1i} \leqq 1\,000\,000\,000 (1 \leqq i \leqq M_{1}).
  • -1\,000\,000\,000 \leqq Y_{2i} \leqq -1 (1 \leqq i \leqq M_{2}).
  • X_{1i} \ne X_{1j} または Y_{1i} \ne Y_{1j} (1 \leqq i, j \leqq M_{1} かつ i \ne j).
  • X_{2i} \ne X_{2j} または Y_{2i} \ne Y_{2j} (1 \leqq i, j \leqq M_{2} かつ i \ne j).
  • 1 \leqq Q \leqq 100\,000.
  • 0 \leqq A_{i} \leqq 1\,000\,000\,000 (1 \leqq i \leqq Q).
  • 任意の 2 つの回線は端点同士以外で共有点を持たない.
  • 系統 1 の回線のみを考えても,系統 2 の回線のみを考えても,任意の 2 つの村及びハブは通信可能である.

小課題

小課題 1 [20 点]

以下の条件を満たす.

  • N, M_{1}, M_{2} \leqq 1\,000.
  • Q \leqq 1\,000.

小課題 2 [80 点]

追加の制限はない.

入出力例

入力例 1

4 3 3 1
1 1
3 2
2 3
1 1 1
1 2 1
1 3 2
1 4 2
2 1 3
2 2 3
3 -1
2 -2
1 -3
1 1 3
1 2 2
1 3 1
1 4 1
2 1 2
2 2 3
2

出力例 1

-2

この入力例は,問題文中の例 1 に対応している.

入力例 2

6 4 5 4
2 1
4 1
3 3
5 2
1 1 1
1 2 1
1 3 2
1 4 2
2 2 4
1 5 4
1 6 4
2 1 3
2 4 3
3 -3
5 -1
2 -2
2 -1
4 -2
1 2 4
1 3 4
1 1 4
2 1 3
1 5 2
1 6 2
1 4 5
2 2 5
1 3 1
2 5 1
3
1
2
0

出力例 2

0
-2
-1
-3

この入力例は,問題文中の例 2 に対応している.


Source Name

JOI 2012/2013 春季トレーニング合宿 Contest Day1