#P13311. [2025年队测]传送

    ID: 12495 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-裴蜀等式欧几里得算法可持久化线段树路径复制二分答案二分查找不变量分析

[2025年队测]传送

题目描述

可爱小苹果和黑黑布莱克分别位于数轴上不同的坐标 A,BA,B。他们想要见面,但只能通过传送器移动。

有 NN 个传送器,第 ii 个传送器位于坐标 cic_i,频率为 fif_i。在一次询问中,只有频率属于 [L,R][L,R] 的传送器可以使用。使用位于 cic_i 的传送器,会把坐标 x1x_1 传送到坐标 x2x_2,其中 x1+x22=ci\frac{x_1+x_2}{2}=c_i。

在每一轮中,两人同时各自选择一个可用的传送器 p,qp,q,可以选择同一个。传送后,本轮产生的疲劳值为 ∣fp−fq∣|f_p-f_q|。他们可以反复传送,直到抵达同一坐标。整个过程的疲劳值是各轮疲劳值的最大值。

给定 QQ 次询问。对于每次询问给出的 A,B,L,RA,B,L,R,求两人能见面时的最小总疲劳值。若无法见面,输出 -1。

输入格式

第一行两个整数 N,QN,Q。

第二行 NN 个整数 c1,c2,…,cNc_1,c_2,\ldots,c_N。

第三行 NN 个整数 f1,f2,…,fNf_1,f_2,\ldots,f_N。

接下来 QQ 行,每行四个整数 A,B,L,RA,B,L,R,保证 A≠BA\ne B。

输出格式

输出一行 QQ 个整数,按询问顺序给出答案。

样例

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 个传送器,可在坐标 99 相遇,疲劳值为 33。若分别使用第 1、3 个传送器,可在坐标 55 相遇,疲劳值为 22。第二次询问的频率区间不允许后一种选择。第三次询问只有一个传送器可用,两人无法见面。

原题另列样例 3 至 7,对应子任务 1、2、7、9、10。

数据规模与约定

对于全部数据,2≤N≤5×1042\le N\le 5\times10^4,1≤Q≤5×1041\le Q\le 5\times10^4,1≤fi≤1091\le f_i\le 10^9,−109≤ci,A,B≤109-10^9\le c_i,A,B\le 10^9,1≤L≤R≤1091\le L\le R\le10^9。原样例 2 的第二次询问使用 L=0L=0,照原样例保留。

原赛子任务 特殊性质 原赛分值
1 N,Q≤10N,Q\le10,∣ci∣,fi≤50\lvert c_i\rvert,f_i\le50 10
2 N≤100N\le100,L=1L=1,R=109R=10^9,∣ci∣,fi≤100\lvert c_i\rvert,f_i\le100
3 N=2N=2,L=1L=1,R=109R=10^9 5
4 N≤103N\le10^3,L=1L=1,R=109R=10^9,fi=1f_i=1 10
5 L=1L=1,R=109R=10^9,fi=1f_i=1
6 N≤103N\le10^3,L=1L=1,R=109R=10^9
7 L=1L=1,R=109R=10^9 15
8 L=1L=1 5
9 N,Q≤2×104N,Q\le2\times10^4 10
10 无特殊限制 15

原题 PDF