以下是来自日本的原始新闻PDF,已完整保存和染色。



可复制的 PDF 提取文本
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 2 – Two Antennas
ふたつのアンテナ(Two Antennas)
JOI 国には直線上に1 km おきに並んだN 個のアンテナが立っている.アンテナには端から順に1 からN
までの番号が付けられている.アンテナi (1 ≦i ≦N) の高さはHi であり,水平距離がAi km 以上Bi km 以
下のアンテナに電波を送ることができる.アンテナx, y (1 ≦x < y ≦N) が相互に電波を送れるとき,この
アンテナのペアは通信を行っており,通信のしにくさが|Hx −Hy| と定義される.
JOI 国の大臣であるK 理事長は,国民から電波が悪いという苦情をQ 個受け取った.様々な調査の結果,
j 個目(1 ≦j ≦Q) の苦情についてはアンテナLj, L j + 1, . . . , Rj のどこかに問題がありそうだということが
わかった.あなたの仕事は,各j (1 ≦j ≦Q) について,アンテナLj, L j + 1, . . . , Rj の中に通信を行ってい
るアンテナのペアが存在するか判定し,存在する場合はそのようなペアの中での通信のしにくさの最大値を
求めることである.
アンテナの情報と苦情の情報が与えられたとき,各苦情について,アンテナLj, Lj + 1, . . . , Rj の中に通信
を行っているアンテナのペアが存在するかを判定し,存在する場合はそのようなペアの中での通信のしにく
さの最大値を求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.入力の値はすべて整数である.
N
H1 A1 B1
...
HN AN BN
Q
L1 R1
...
LQ RQ
出力
標準出力にQ 行出力せよ.j 行目(1 ≦j ≦Q) には,アンテナLj, Lj + 1, . . . , R j の中に通信を行ってい
るペアが存在しない場合は−1 を,存在する場合はそのようなペアの中での通信のしにくさの最大値を出力
せよ.
ふたつのアンテナ– 1 / 3
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 2 – Two Antennas
制約
• 2 ≦N ≦200 000.
• 1 ≦Hi ≦1 000 000 000 (1 ≦i ≦N).
• 1 ≦Ai ≦Bi ≦N −1 (1 ≦i ≦N).
• 1 ≦Q ≦200 000.
• 1 ≦L j < R j ≦N (1 ≦j ≦Q).
小課題
1. (2 点) N ≦300,Q ≦300.
2. (11 点) N ≦2 000.
3. (22 点) Q = 1,L1 = 1,R1 = N.
4. (65 点) 追加の制約はない.
入出力例
入力例1 出力例1
5 -1
10 2 4 1
1 1 1 8
2 1 3 8
1 1 1 99
100 1 1
5
1 2
2 3
1 3
1 4
1 5
アンテナ1 とアンテナ2 の間では通信を行っていない.1 個目の答えは−1 である.
2, 3, 4, 5 個目の答えとなるアンテナのペアは,それぞれ(2, 3), (1, 3), (1, 3), (4, 5) である.
ふたつのアンテナ– 2 / 3
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 2 – Two Antennas
入力例2 出力例2
20 806460109
260055884 2 15
737689751 5 5
575359903 1 15
341907415 14 14
162026576 9 19
55126745 10 19
95712405 11 14
416027186 8 13
370819848 11 14
629309664 4 13
822713895 5 15
390716905 13 17
577166133 8 19
195931195 10 17
377030463 14 17
968486685 11 19
963040581 4 10
566835557 1 12
586336111 6 16
385865831 8 9
1
1 20
この入力例は小課題3 の制約を満たす.
ふたつのアンテナ– 3 / 3