#3258. 「ROIR 2020 Day 1」超速

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: ShineEternal

题目描述

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

超速行驶是一种危险的犯法行为,大大增加了交通事故导致悲惨后果的可能性。为了防止这种行为的出现,需要对汽车进行区间测速。

现在有 n 段从 1\sim n 编号的公路。第 i 段公路长 l_i 米,其限速为 v_i 米每秒。超速就要罚款,但是为了体现公平公正,还要对不同程度的超速设置不同的罚款金额。

e 表示汽车在这段公路上的最大超速值,即将任意时刻汽车的速度减去路段限速,这一值在整个时间段上取到的最大值。如果不超速则不收罚款,否则:

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

  • 如果 a_1<e\leq a_2 ,则惩罚为 f_2 个货币单位。

  • ...

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

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

目前,有 q 辆车要经过这 n 段道路,每辆车在 s_i 时间到达 1 号路段,在 t_i 时间离开 n 号路段。

你需要计算每辆车最高被罚款的金额。

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

输入格式

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

接下来的两行,每行 n 个数,第一行为 v_i ,第二行为 l_i

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

接下来的两行,第一行 m-1 个数,为 a_i ;第二行 m 个数,为 f_i

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

接下来的 q 行,每行两个整数 s_i,t_i

输出格式

输出共 q 行。

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

样例

样例输入

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\% 的数据, 1\leq n\leq 10 1\leq v_i,l_i,a_i,f_i\leq 10^9 1\leq m\leq 10^5 1\leq s_i<t_i\leq 10^9 1\le q\le 10^5

任务编号 特殊限制 分值
1 n=1,m=1 5
2 m=1 10
3 n=1,m\leq 10 9
4 n=1 12
5 m\leq 10,a_i\leq 10 13
6 m\leq 10 14
7 无特殊限制 37