奇怪的基站
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
奇怪的基站
题目背景
题目描述
小明在A城的电信公司工作,负责维护一条街道的基站通信设备。这条街道有编号~的个基站均匀分布在街道一侧,号基站到号基站的距离为。这个公司的基站很奇怪,第个基站在高度为的地方,而且它只能向和它距离在之间的基站传输信息。同时,这些基站水平传递信息的能力强而垂直传递信息的能力弱,因此如果两个基站和之间能够互相传递信息,那么它们之间传递信息需要一个成本。
然而今天有些基站坏了,小明焦头烂额。他收到了条投诉,第条投诉说区间里出现了故障。为了排除故障,你需要知道这些区间内是否存在一对基站可以互相通信,如果有,你要找到能通信的基站的最大通信成本。
输入格式
第一行一个正整数。之后行每行三个正整数。再之后一个正整数,之后行每行两个正整数。
输出格式
行,每行一个整数表示能通信的基站的最大通信成本。如果不存在一对能通信的基站,输出。
样例 #1
样例输入 #1
3
1 2 2
2 1 1
3 1 2
3
1 2
2 3
1 3
样例输出 #1
-1
1
2
提示
样例解释1
第1个基站能和第3个基站通信,所以询问区间为[1,2]时,1号无法向2号通信,所以输出-1。
第2个基站能和第1,3个基站通信,第3个基站能和第1,2个基站通信,所以询问区间为[2,3]时,输出2和3的通信成本1;询问成本为[1,3]时,由于1和3能互相通信,所以输出1和3的通信成本2。
数据范围
对的数据,。
对的数据,。
对另外的数据,。
对的数据,$2≤n≤200000,1≤h_i≤10^9,1≤a_i≤b_i≤n-1,1≤q≤200000,1≤L_j≤R_j≤n$。
国庆集训S组模拟赛1
- Status
- Done
- Rule
- OI
- Problem
- 4
- Start at
- 2023-10-5 9:00
- End at
- 2023-10-5 17:00
- Duration
- 4 hour(s)
- Host
- Partic.
- 51