#3033. 「JOISC 2019 Day2」两个天线

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: WAAutoMaton

题目描述

题目译自 JOISC 2019 Day2 T1「ふたつのアンテナ / Two Antennas

N 个天线排成一行,编号分别为 1 N ,相邻两个天线之间的距离都是 1 。天线 i 的高度为 H_i 。天线 i 可以向天线 j 发送信息,当且仅当他们之间的距离 D_{i,j} \in [A_i, B_i] 。如果一对天线 i j 可以互相发消息,那么我们定义他们之间的通信成本为 \lvert H_i - H_j \rvert

JOI 共和国总理 K 先生收到了 Q 件通信故障的投诉,对于第 j 件投诉,你需要确定天线 L_j, L_j+1, \ldots , R_j​ 中是否存在一对天线可以互相发消息,如果存在,输出最大的通信成本。

输入格式

从标准输入中读取数据。

第一行一个整数 N

接下来 N 行,第 i 行三个整数 H_i, A_i, B_i

接下来一行一个整数 Q

接下来 Q 行,第 j 行两个整数 L_j, R_j

输出格式

输出数据到标准输出中。

输出 Q 行,第 j 行一个整数,表示第 j 件投诉的最大通信成本,如果不存在可以互相发消息的天线,输出 -1

样例

样例输入 1
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5
样例输出 1
-1
1
8
8
99
样例说明 1

天线 1 和天线 2 无法互相发消息,因此第一个询问答案为 -1

对于第 2, 3, 4, 5 个询问,能产生最大通信成本的天线对分别为 (2, 3), (1, 3), (1,3), (4, 5)

样例输入 2
20
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
样例输出 2
806460109
样例说明 2

这组样例满足子任务 3 的限制。

数据范围与提示

Subtask # 分值 数据规模
1 2 N,Q \le 300
2 11 N \le 2 000
3 22 Q = 1, L_1 = 1, R_1 = N
4 65 无特殊限制

对于所有输入数据,有
2 \le N \le 200 000, \\ 1 \le H_i \le 10^9 (1 \le i \le N), \\ 1 \le A_i \le B_i \le N-1 (1 \le i \le N), \\ 1 \le Q \le 200 000, \\ 1 \le L_j \le R_j \le N (1 \le j \le Q).