#PQJ1545x65. QOJ 1545_65
QOJ 1545_65
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 There are N antennas, numbered from 1 to N along a line. Each antenna is one kilometer distant from consecutive antennas. The height of the antenna i (1 ≤i ≤N) is Hi. The antenna i can send information to the antennas located between Ai kilometers and Bi kilometers, inclusive, from the antenna i. If and only if the antenna x and the antenna y (1 ≤x < y ≤N) can send information to each other, the pair of antennas is in communication, and the communication cost is equal to |Hx −Hy|. Mr. K, the Prime Minister of JOI Republic, has received Q complaints about bad connection from the citizens. A study showed that, for the j-th complaint (1 ≤j ≤Q), something among the antennas L j, Lj + 1, . . . , Rj has troubles. You are assigned to find whether there exists a pair of antennas in communication among the antennas Lj, L j + 1, . . . , Rj, and if there does, you also have to find the maximum communication cost among such pairs. Write a program which, given the information of antennas and complaints, determines whether there ex- ists a pair of antennas in communication among the antennas Lj, Lj + 1, . . . , Rj and calculates the maximum communication cost among such pairs if there exists such a pair. Input Read the following data from the standard input. All the values in the input are integers. N H1 A1 B1 ... HN AN BN Q L1 R1 ... LQ RQ Output Write Q lines to the standard output. The j-th line (1 ≤j ≤Q) should be −1 if there is no pair of antennas in communication among the antennas Lj, L j + 1, . . . , Rj, or the maximum communication cost among such pairs otherwise. Two Antennas– 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 Constraints • 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). Subtasks
- (2 points) N ≤300, Q ≤300.
- (11 points) N ≤2 000.
- (22 points) Q = 1, L1 = 1, R1 = N.
- (65 points) No additional constraints. Sample Input and Output Sample Input 1 Sample Output 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 The antenna 1 and the antenna 2 are not in communication, so the answer to the 1st complaint is −1. The pair of antennas in communication which has the maximum communication cost for the 2nd, 3rd, 4th and 5th complaint is (2, 3), (1, 3), (1, 3), and (4, 5), respectively. Two Antennas– 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 Sample Input 2 Sample Output 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 This sample input satisfies the constraints for Subtask 3. Two Antennas– 3 / 3