← 返回题目列表

AtCoder · joisc2019_d

D. 两个天线

中文机器翻译题面 查看原题

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

ふたつのアンテナ (Two Antennas) - 原题 PDF 第 1 页
原题PDF第1页
ふたつのアンテナ (Two Antennas) - 原题 PDF 第 2 页
原题PDF第2页
ふたつのアンテナ (Two Antennas) - 原题 PDF 第 3 页
原题PDF第3页
可复制的 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