题目描述
可爱小苹果和黑黑布莱克分别位于数轴上不同的坐标 A,B。他们想要见面,但只能通过传送器移动。
有 N 个传送器,第 i 个传送器位于坐标 ci,频率为 fi。在一次询问中,只有频率属于 [L,R] 的传送器可以使用。使用位于 ci 的传送器,会把坐标 x1 传送到坐标 x2,其中 2x1+x2=ci。
在每一轮中,两人同时各自选择一个可用的传送器 p,q,可以选择同一个。传送后,本轮产生的疲劳值为 ∣fp−fq∣。他们可以反复传送,直到抵达同一坐标。整个过程的疲劳值是各轮疲劳值的最大值。
给定 Q 次询问。对于每次询问给出的 A,B,L,R,求两人能见面时的最小总疲劳值。若无法见面,输出 -1。
输入格式
第一行两个整数 N,Q。
第二行 N 个整数 c1,c2,…,cN。
第三行 N 个整数 f1,f2,…,fN。
接下来 Q 行,每行四个整数 A,B,L,R,保证 A=B。
输出格式
输出一行 Q 个整数,按询问顺序给出答案。
样例
4 3
4 6 8 10
7 1 9 4
3 11 1 50
3 11 1 5
5 7 1 1
2 3 -1
3 3
-2 1 -1
10 1 3
-6 6 20 20
-6 6 0 20
-6 6 2 20
-1 2 7
样例 1 的第一次询问,两人分别使用第 2、4 个传送器,可在坐标 9 相遇,疲劳值为 3。若分别使用第 1、3 个传送器,可在坐标 5 相遇,疲劳值为 2。第二次询问的频率区间不允许后一种选择。第三次询问只有一个传送器可用,两人无法见面。
原题另列样例 3 至 7,对应子任务 1、2、7、9、10。
数据规模与约定
对于全部数据,2≤N≤5×104,1≤Q≤5×104,1≤fi≤109,−109≤ci,A,B≤109,1≤L≤R≤109。原样例 2 的第二次询问使用 L=0,照原样例保留。
| 原赛子任务 |
特殊性质 |
原赛分值 |
| 1 |
N,Q≤10,∣ci∣,fi≤50 |
10 |
| 2 |
N≤100,L=1,R=109,∣ci∣,fi≤100 |
| 3 |
N=2,L=1,R=109 |
5 |
| 4 |
N≤103,L=1,R=109,fi=1 |
10 |
| 5 |
L=1,R=109,fi=1 |
| 6 |
N≤103,L=1,R=109 |
| 7 |
L=1,R=109 |
15 |
| 8 |
L=1 |
5 |
| 9 |
N,Q≤2×104 |
10 |
| 10 |
无特殊限制 |
15 |
原题 PDF