← 返回题目列表

AtCoder · pakencamp_2025_day2_b

B. 蚂蚁序列

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

配点 : 100 点

問題文

称为帕肯蚂蚁的蚂蚁生活在帕肯王国。帕肯阿里很长 创建一个又长又细的嵌套 M ,该嵌套将协调左端。 0,坐标右边缘 它用 M 表示为数轴。

生物学家Paken先生发现Paken蚂蚁有以下习性。

  • Paken Ari 朝您当前在数轴上面对的方向移动。 以 1 每秒 1 的速度前进。
  • 2 当两只帕肯蚁在某一时刻到达同一坐标时,2 蚂蚁们立即改变方向,没有互相经过。此外,由于条件限制,3 保证不会有超过一只帕肯蚂蚁同时到达同一坐标。
  • 每只帕肯蚂蚁都位于巢穴的左边缘(坐标 0)或右边缘(坐标 M),行进方向立即反转。

现在,Phaken 先生 我正在考虑 Q 问题。i (1 \leq i \leq Q) 为整数 给出 l_i 和 将其放在 r_i 并具有以下内容。 帕肯·阿里 (Paken Ari) 上

  • 座標 A_{l_i}, A_{l_i+1}, \dots, A_{r_i} 帕肯·阿里托 1 将它们一一面向右放置。t 秒后,原始坐标 A_j (l_i \leq j \leq r_i中的所有蚂蚁同时设置它们的坐标。 一个非负整数,如 B_j 判断 t 的最小值是否存在,如果存在,则求最小值。 查找所有

Q 问题的答案。

制約

  • 1 \le N, M, Q \le 4 \times {10}^5
  • 0 < A_i < M \ (1 \le i \le N)
  • A_i \neq A_j \ (i \neq j)
  • 0 \le B_j \le M \ (1 \le j \le N)
  • 1 \le l_i \le r_i \le N \ (1 \le i \le Q)
  • 所有输入均为整数。

小課題

  1. (4 点) N,M \leq 1000,Q \leq 10
  2. (8 点) N \leq 1000,Q \leq 10
  3. (26 点) Q \leq 10
  4. (30 点) N,M,Q \leq {10}^5,A_i < A_{i+1} \ (1 \leq i < N),B_j \leq B_{j+1} \ (1 \leq j < N)
  5. (20 点) N,M,Q \leq {10}^5
  6. (12 点)无附加约束

入力

输入将以以下形式通过标准输入给出。

N M Q
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N
l_1 r_1
l_2 r_2
\vdots
l_Q r_Q

出力

Q 行。 当 i (1 \leq i \leq Q) 行包含 作为第i 问题的答案,最小 将 t 作为整数打印。如果这样的话 对于第 t 不存在,则 输出 -1 。


入力例 1

4 20 3
1 4 10 15
5 8 17 18
1 4
1 2
3 4

出力例 1

-1
4
7

1 个问题,所有 坐标关于 i 位于 A_i 的 Paken Ari 有坐标 最小的,例如 B_i 最小的这样 t 不存在。因此,答案是 对于第 -1 。

2 个问题,4 秒后,坐标 1 处的蚂蚁有坐标 5 ,坐标 前往 4 处的蚂蚁有坐标 8 并满足条件。这是最小的 由于可以证明 t ,所以答案是 通过使用 4 。

3 个问题,7 秒后,坐标 10 处的蚂蚁有坐标 17 ,坐标 前往 15 处的蚂蚁有坐标 M 反转行进方向进行协调 18 并满足条件。这是最小的 由于可以证明 t ,所以答案是 通过使用 7 。