#D. 奇怪的基站

    Type: Default 3000ms 512MiB

奇怪的基站

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城的电信公司工作,负责维护一条街道的基站通信设备。这条街道有编号11~nnnn个基站均匀分布在街道一侧,ii号基站到i+1i+1号基站的距离为11。这个公司的基站很奇怪,第ii个基站在高度为hih_i的地方,而且它只能向和它距离在[ai,bi][a_i,b_i]之间的基站传输信息。同时,这些基站水平传递信息的能力强而垂直传递信息的能力弱,因此如果两个基站iijj之间能够互相传递信息,那么它们之间传递信息需要一个成本hihj|h_i-h_j|

然而今天有些基站坏了,小明焦头烂额。他收到了qq条投诉,第jj条投诉说[Lj,Rj][L_j,R_j]区间里出现了故障。为了排除故障,你需要知道这些区间内是否存在一对基站可以互相通信,如果有,你要找到能通信的基站的最大通信成本。

输入格式

第一行一个正整数nn。之后nn行每行三个正整数hi,ai,bih_i,a_i,b_i。再之后一个正整数qq,之后qq行每行两个正整数Lj,RjL_j,R_j

输出格式

qq行,每行一个整数表示能通信的基站的最大通信成本。如果不存在一对能通信的基站,输出1-1

样例 #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。

数据范围

5%5\%的数据,n,q300n,q≤300

15%15\%的数据,n2000n≤2000

对另外20%20\%的数据,q=1,L1=1,R1=Nq=1,L_1=1,R_1=N

100%100\%的数据,$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

Not Attended
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