Задача 2. Превышение скорости ≡

Условие

Превышение скорости является опасным нарушением, значительно увеличивающим вероятность трагических последствий транспортных происшествий. К сожалению контроль скорости с использованием радаров и камер не решает проблему полностью. Притормаживая перед камерами, водители едут со значительным превышением на участках дорог, где контроль не ведётся. С целью предотвращения такого поведения используется назначение штрафа за гарантирование превышение скорости, основанное на времени проезда дороги.

Рассмотрим дорогу, состоящую из n участков, пронумерованных от 1 до n. Длина i-го участка составляет l_i метров. На i-м из участков установлено ограничение по скорости в v_i м/с.

За превышение скорости предусмотрены штрафы. В зависимости от превышения, установлены различные штрафы, величина штрафа вычисляется следующим образом.

Пусть e — максимальное превышение разрешённой скорости в процессе пребывания автомобиля на всей дороге, то есть максимальная разница между скоростью автомобиля и максимальной разрешенной скоростью на участке, где он в этот момент находится. Если превышения скорости не было, то штраф не взимается. В противном случае штраф вычисляется так:

• если 0 < e ≤ a₁, то штраф составляет f₁ денежных единиц
• если a₁ < e ≤ a₂, то штраф составляет f₂ денежных единиц
• …
• если a_m − 2 < e ≤ a_m − 1, то штраф составляет f_m − 1 денежных единиц
• если a_m − 1 < e, то штраф составляет f_m денежных единиц

Таким образом, есть m диапазонов превышения скорости и соответствующие им штрафы.

Автоматическая система назначения штрафов получила данные о q автомобилях. Для удобства пронумеруем их от 1 до q. Известно, что i-й автомобиль заехал на дорогу в момент времени s_i, проехал все n участков, после чего выехал с нее в момент времени t_i. Отсчёт времени будем вести в секундах с открытия дороги.

Для каждого из автомобилей система должна определить, какой максимальный штраф можно гарантированно выписать этому автомобилю, основываясь только на времени заезда на дорогу и выезда с нее.

Требуется написать программу, которая по описанию границ диапазонов превышения скорости, соответствующих штрафов и временам въезда/выезда автомобилей определяет для каждого автомобиля максимальный штраф, который можно выписать этому автомобилю.

Формат входных данных

Первая строка входных данных содержит единственное целое число n — количество участков на дороге.

Вторая строка содержит n целых чисел v_i — ограничения скорости на участках.

Третья строка содержит n целых чисел l_i — длины участков.

Четвертая строка содержит единственное целое число m — количество границ диапазонов превышения скорости.

Пятая строка содержит m − 1 целых чисел a_i — границы диапазонов превышения скорости. Гарантируется, что значения a_i строго возрастают. Обратите внимание, что если m = 1, то пятая строка ввода пустая.

Шестая строка содержит m целых чисел f_i — штрафы за диапазоны превышения скоростей. Гарантируется, что значения f_i возрастают.

Седьмая строка содержит единственное целое число q — количество автомобилей, которые надо обработать.

Каждая из следующих q строк содержит два целых числа s_i и t_i — время заезда на трассу и выезда с неё i-го из рассматриваемых автомобилей .

Формат выходных данных

Для каждого из q автомобилей выведите в отдельной строке максимальный штраф, который гарантированно можно выписать этому автомобилю, основываясь только на временах его заезда на дорогу и выезда с нее. Если возможна ситуация, что автомобиль ни разу не превысил разрешённую скорость, следует вывести 0.

Гарантируется, что если время въезда или выезда автомобиля изменить не более чем на 10^− 5, штраф, который можно ему выписать, не изменится.

Ограничения

1 ≤ n ≤ 10

1 ≤ v_i, l_i, a_i, f_i ≤ 10⁹

1 ≤ m, q ≤ 10⁵

1 ≤ s_i < t_i ≤ 10⁹

Система оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

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

Разбор

Предположим, максимальное превышению скорости автомобиля на дороге не превышает d. Это значит, что на i-м участке автомобиль ехал со скоростью не выше v_i + d и проехал его за время не меньше l_iv_i + d. Общее время, за которое автомобиль проедет дорогу не меньше ∑_il_iv_i + d.

Таким образом, превышение не больше чем на d возможно, если s + ∑_il_iv_i + d ≥ t.

Решение за O(nmq): для каждой верхней границы отрезков штрафов проверим, возможно ли, чтобы автомобиль превышал не более чем на d. Заметим, что если для некоторого i невозможно, чтобы превышение было не больше a_i − 1, то гарантировано можно назначить автомобилю штраф f_i. Из всех таких значений надо выбрать максимальное возможное.

Заметим, что проверку можно делать с использованием вещественной арифметики, не опасаясь проблем с точностью, благодаря ограничению в условии, что небольшое изменение времени въезда или выезда во входных данных не может изменить штраф.

Это решение проходит все подзадачи, кроме подзадачи 7.

Чтобы решить подзадачу 7, заметим, что свойство "можно проехать с превышением не больше d" является монотонным: если можно проехать с превышением не больше d, то можно проехать с превышением не больше d′ для всех d′ ≥ d. Поэтому для определения максимального возможного штрафа можно применить двоичный поиск. Полученное решение работает за O(nqlog m).

Отметим также частичные решения, решающие некоторые подзадачи.

Для решения подзадач с n = 1 можно воспользоваться тем, что в этом случае мы можем легко вычислить превышение: d = max(0, (t − s) / l₁).

В подзадачах с m = 1 требуется лишь проверить, есть ли превышение. Для этого можно вычислить, за какое время может проехать дорогу автомобиль, соблюдающий ограничения скорости.

В подзадаче 5 можно применить линейный поиск вместо двоичного, перебрав значения d превышения от 0 до 10.