#P9784. [ROIR 2020 Day1] 超速

[ROIR 2020 Day1] 超速

题目描述

译自 ROIR 2020 Day1 T2. Превышение скорости ,译者 ShineEternal

超速行驶是一种危险的犯法行为,大大增加了交通事故导致悲惨后果的可能性。不幸的是使用使用雷达和相机控制速度并不能完全解决问题。为了防止这种行为的出现,根据汽车在一段道路上的行驶时间来罚款,可以对超速行为进行限制。

现在有 nn 段从 1n1\sim n 编号的公路。第 ii 段公路长 lil_i 米,其限速为 viv_i 米每秒。超速就要罚款,但是为了体现按劳分配,还要对不同程度的超速设置不同的罚款金额。

具体来说,如果不超速则不收罚款;否则,用 ee 表示汽车在这段公路上的最大速度减去限速的值:

  • 如果 0<ea10<e\leq a_1,则惩罚为 f1f_1 个货币单位。

  • 如果 a1<ea2a_1<e\leq a_2,则惩罚为 f2f_2 个货币单位。

  • ...

  • 如果 am2<eam1a_{m-2}<e\leq a_{m-1},则惩罚为 fm1f_{m-1} 个货币单位。

  • 如果 am1<ea_{m-1}<e,则惩罚为 fmf_m 个货币单位。

目前,有 qq 辆车要经过这 nn 段道路,每辆车在 sis_i 时间到达 11 号路段,在 tit_i 时间离开 nn 号路段。

你需要计算每辆车在所有路段中最高被罚款的金额至少是多少。

时间从道路开放起计算,即从 00 开始计算。

输入格式

第一行一个正整数 nn,表示道路段数。

接下来的两行,每行 nn 个数,第一行为 viv_i,第二行为 lil_i

第四行为一个正整数 mm,表示罚款的 mm 种不同范围。

接下来的两行,第一行 m1m-1 个数,为 aia_i;第二行 mm 个数,为 fif_i

第七行为一个正整数 qq,表示共有 qq 辆车。

接下来的 qq 行,每行两个整数 si,tis_i,t_i

输出格式

输出共 qq 行。

对于每辆车,输出它最少被罚款的金额。

3
10 20 30
400 500 600
6
1 5 10 12 16
100 300 600 800 1000 1500
3
10 100
20 70
45 100
0
800
600

提示

对于 100%100\% 的数据,1n101\leq n\leq 101vi,li,ai,fi1091\leq v_i,l_i,a_i,f_i\leq 10^91m1051\leq m\leq 10^51q1051\le q\le 10^51si<ti1091\leq s_i<t_i\leq 10^9

任务编号 特殊限制 分值
11 n=1,m=1n=1,m=1 55
22 m=1m=1 1010
33 n=1,m10n=1,m\leq 10 99
44 n=1n=1 1212
55 m10,ai10m\leq 10,a_i\leq 10 1313
66 m10m\leq 10 1414
77 无特殊限制 3737