33OJ
登录 注册

#P17545. [JAG 2026 Summer Camp #2] Robot Damage

[JAG 2026 Summer Camp #2] Robot Damage

题目描述

某实验室有一条可以视为数轴的直线测试轨道,以及一个沿轨道移动的机器人。每次实验开始时,机器人都静止在原点。

轨道上放置了两面墙,一面位于负坐标,另一面位于正坐标。机器人无法穿过墙,只能在两面墙之间的闭区间内移动。

机器人上有一个按钮。按下按钮后,机器人依次执行以下 NN 个阶段。

  • 假设第 ii 个阶段开始时机器人位于坐标 XX。它尝试沿数轴向坐标 X+ViX+V_i 移动。若 Vi>0V_i>0,则向右移动;若 Vi<0V_i<0,则向左移动。
  • 如果没有墙阻挡,机器人用一分钟抵达目标位置。在阶段开始时,它的速度为零,随后加速、减速,并以零速度抵达目标位置。在移动过程的每个中间位置,它的速度都大于零。
  • 如果一面墙严格位于当前位置和目标位置之间,机器人就会在移动过程中撞上墙,并在墙边结束当前阶段。

完成全部 NN 个阶段后,机器人停在当前位置。若再次按下按钮,它就从该位置出发,再执行一遍相同的 NN 个阶段。

每当机器人以正速度撞上墙时,就会受到一点伤害。但在以下两种情况下,它不会受到伤害。

  • 目标位置恰好位于墙边,因此机器人以零速度抵达墙边。
  • 阶段开始时机器人已经贴着墙,并尝试越过这面墙。此时机器人不会移动。

换言之,当且仅当一面墙严格位于阶段开始时的位置与预定目标位置之间,机器人才会在该阶段受到伤害。只要碰撞时速度为正,伤害量就与具体速度无关。

给定 QQ 次询问,询问之间相互独立。第 ii 次询问描述如下实验。

  • 将墙放在坐标 −Wi-W_i 和 WiW_i,将机器人放在原点。
  • 总共按下按钮 TiT_i 次,每次都等上一次按钮触发的动作完成后再按。两次按按钮之间不移动机器人。

求机器人在这次实验中受到的总伤害。

给定 tt 组测试数据,请分别求解。

输入格式

输入包含一组或多组测试数据。第一行包含一个整数 tt,表示测试数据组数(1≤t≤1051\le t\le 10^5)。随后依次给出各组测试数据,每组格式如下。

N
V_1 V_2 ... V_N
Q
W_1 T_1
W_2 T_2
...
W_Q T_Q

整数 NN 表示每次按下按钮后执行的阶段数(1≤N≤2×1051\le N\le 2\times 10^5)。对于每个 i=1,…,Ni=1,\ldots,N,整数 ViV_i 表示第 ii 个阶段尝试移动的位移(−109≤Vi≤109-10^9\le V_i\le 10^9,Vi≠0V_i\ne 0)。

整数 QQ 表示询问次数(1≤Q≤2×1051\le Q\le 2\times 10^5)。对于每个 i=1,…,Qi=1,\ldots,Q,整数 Wi,TiW_i,T_i 分别表示第 ii 次询问中原点到每面墙的距离以及按按钮的次数(1≤Wi≤10161\le W_i\le 10^{16},1≤Ti≤10121\le T_i\le 10^{12})。

所有测试数据的 NN 之和不超过 4×1054\times 10^5,QQ 之和不超过 4×1054\times 10^5。

输出格式

对于每组测试数据,输出 QQ 行。第 ii 行包含第 ii 次询问的答案。

4
4
1 -8 6 -7
2
5 1
9 2
3
1 -2 1
1
1 100
2
3 4
2
8 2
8 10000
2
1000000000 -1000000000
1
10 1000000000000
2
2
0
1
1
2000000000000

提示

在第一组测试数据中,第 11 次询问会在第 22 和第 44 个阶段于 −5-5 处发生碰撞,共受到 22 点伤害。第 22 次询问中,两次在 −9-9 处发生的碰撞都出现在第二次按下按钮之后。

在第二组测试数据中,机器人从未以正速度撞上墙,因此没有受到伤害。