← 返回题目列表

AtCoder · pakencamp_2022_day2_c

C. 合作

中文机器翻译题面 查看原题

配点 : 600 点

問題文

帕肯镇是帕肯艺术博物馆和驹场艺术博物馆的所在地。每个博物馆都有 N 艺术品从帕肯艺术博物馆的左侧开始连续展示。 第 i 件艺术品的价值是 A_i 从驹场博物馆左侧开始 i 件艺术品的价值是 B_i 。为了进一步娱乐参观者,艺术品从左到右按照价值从低到高的顺序排列。

帕肯美术馆和驹场美术馆将举办合作展览。为了合作 有 Q 计划可用。 i 第二张平面图中,从公园博物馆左边开始 L_i 起 R_i 艺术品和驹场博物馆左侧 第 X_i 起 Y_i 部艺术作品将展出。同样,在合作展览中,艺术品也会按照价值从低到高的顺序从左到右排列。

让我们假设一次展览的满意度是相邻艺术品之间价值差异的最小值。每个 i \ (1 \leq i \leq Q) , i 请找出第一个计划参展时的满意度。

制約

  • 所有输入均为整数
  • 1 \leq N \leq 200000
  • 1 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq 10^{18}
  • 1 \leq B_1 \leq B_2 \leq \cdots \leq B_N \leq 10^{18}
  • 1 \leq Q \leq 200000
  • 1 \leq L_i \leq R_i \leq N \ (1 \leq i \leq Q)
  • 1 \leq X_i \leq Y_i \leq N \ (1 \leq i \leq Q)

小課題

  1. (50 点) N, Q \leq 1000
  2. (150 点) \max(A_{L_i}, B_{X_i}) > \min(A_{R_i}, B_{Y_i}) \ (1 \leq i \leq Q)
  3. (400 点)无附加约束

入力

输入将以以下格式从标准输入给出。

N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
Q
L_1 R_1 X_1 Y_1
L_2 R_2 X_2 Y_2
\vdots
L_Q R_Q X_Q Y_Q

出力

Q 行输出。i 行目 (1 \leq i \leq Q) 有 i 输出第h个计划参展时的满意度。 在第


入力例 1

6
1 3 6 8 9 11
2 2 4 7 10 11
4
1 6 2 5
1 6 5 5
2 5 5 5
4 6 3 6

出力例 1

1
1
1
0

1 个计划中,排列的艺术品的价值是 1, 2, 3, 4, 6, 7, 8, 9, 10, 11 。在这种情况下,相邻展品之间价值差的最小值为 满足 1 。

此输入示例是一个小作业。 1, 3 约束。


入力例 2

10
4 14 18 31 47 51 59 72 78 96
2 23 25 36 58 60 63 85 88 97
7
1 3 5 5
6 10 3 4
8 10 1 4
7 10 2 4
6 7 1 3
2 4 6 9
2 3 2 9

出力例 2

4
6
2
2
2
3
2

此输入示例满足所有子任务约束。 请针对


入力例 3

15
1141 1334 2083 2504 4031 4238 4328 5260 5315 6427 6991 8127 8199 8356 9136
189 403 1035 1126 1165 1477 2021 2100 2528 3892 4108 4459 5792 7050 8709
8
4 7 7 15
8 11 8 11
7 11 2 15
2 13 6 11
11 12 3 10
8 10 3 12
3 11 3 10
3 11 8 10

出力例 3

24
55
39
17
39
39
17
17

此输入示例是一个小作业。 1, 3 约束。