Всероссийская олимпиада школьников

Задача №115235. Гонка дронов

В Иннополисе проводятся гонки дронов.

В гонке могут принять участие $n$ дронов, $i$-й дрон пролетает единицу расстояния за $t_i$ секунд. Гонка проводится на прямой, на которой расположены $m$ ворот, пронумерованных от $1$ до $m$, $i$-е ворота находятся на расстоянии $s_i$ от стартовой позиции гонки.

В гонке примут участие первые $k$ дронов с номерами от $1$ до $k$. Величину $k$ судьи объявляют непосредственно перед гонкой, поэтому вам необходимо проанализировать гонку для всех $k$ от $1$ до $n$.

Гонка проводится следующим образом.

Дроны начинают движение из точки $0$ в сторону ворот, каждый со своей скоростью. У каждого дрона есть точка восстановления — последние ворота, в которых он выполнял сохранение позиции . Изначально точка восстановления каждого дрона — точка $0$. Дроны каждый раз начинают двигаться из своих точек восстановления и продолжают движение, пока один или несколько дронов не оказываются в точке, где расположены ворота (возможно, различные для разных дронов). В этот момент среди всех дронов, которые оказались в каких-либо воротах, выбирается дрон с наименьшим номером. Для этого дрона производится сохранение позиции, его точка восстановления переносится в его текущую позицию. Остальные дроны мгновенно телепортируются в свои точки восстановления. После этого гонка продолжается таким же образом.

Как только дрон сохраняет позицию в последних воротах с номером $m$, он финиширует. Не финишировавшие пока дроны, как обычно, телепортируются в свои точки восстановления и продолжают гонку. Когда все дроны финишируют, гонка завершается.

Телепортация — очень энергоемкий процесс. Для подготовки к гонке необходимо понять, сколько суммарно телепортаций совершат все дроны до её завершения. Обозначим как $c_k$ суммарное число телепортаций, которое совершат все дроны, если в гонке будут участвовать первые $k$ дронов. Найдите значения $c_1, c_2, \ldots, c_n$.

Входные данные

В первой строке даны два целых числа $n$ и $m$ — количество дронов и ворот, соответственно ($2 \le n \le 150\,000$, $1 \le m \le 150\,000$).

Во второй строке даны $n$ положительных целых чисел $t_1, t_2,...,t_n$, где $t_i$ — количество секунд, за которое $i$-й дрон пролетает единицу расстояния ($1 \le t_i \le 10^9$).

В третьей строке даны $m$ положительных целых чисел $s_1, s_2,...,s_m$, где $s_i$ — позиция $i$-х ворот на прямой ($1 \le s_1 < s_2 < \ldots < s_m \le 150\,000$).

Выходные данные

Выведите $n$ целых чисел $c_1, c_2, \ldots, c_n$.

Система оценки

		Ограничения
Подз.	Баллы	$n$	$m$	$t_i, s_i$	Доп. ограничения	Необх. подзадачи
1	5	$n = 2$	$m \le 50$	$t_i,s_i \le 100\,000$
2	7	$n \le 50$	$m \le 50$	$t_i,s_i \le 100\,000$		У, 1
3	13	$n \le 1000$	$m \le 5$	$t_i,s_i \le 100\,000$		У
4	9	$n \le 100\,000$	$m \le 100\,000$	$t_i,s_i \le 100\,000$	$s_{i+1} - s_i = s_1$ для всех $1 \le i < m$
5	8	$n \le 100\,000$	$m \le 100\,000$	$t_i,s_i \le 100\,000$	все $t_i$ равны
6	10	$n \le 100$	$m \le 100\,000$	$t_i,s_i \le 100\,000$		У, 1 – 2
7	5	$n \le 100\,000$	$m \le 100\,000$	$t_i \le 2$, $s_i \le 100\,000$
8	7	$n \le 100\,000$	$m=2$	$t_i,s_i \le 100\,000$
9	6	$n \le 10\,000$	$m \le 100\,000$	$t_i,s_i \le 100\,000$		У, 1 – 3, 6
10	6	$n \le 50\,000$	$m \le 100\,000$	$t_i,s_i \le 100\,000$		У, 1 – 3, 6, 9
11	8	$n \le 100\,000$	$m \le 100\,000$	$t_i,s_i \le 100\,000$		У, 1 – 10
12	8	$n \le 100\,000$				У, 1 – 11
13	8	без дополнительных ограничений				У, 1 – 12

Примечание

Рассмотрим первый пример.

Если $k = 1$, то телепортаций не происходит.

Если $k=2$, то гонка происходит следующим образом. На рисунках показаны моменты, когда дроны оказываются в воротах и происходит телепортация.

$\text{[math]}$
$\text{[math]}$
$\text{[math]}$	1 телепортация
$\text{[math]}$
$\text{[math]}$	+1 телепортация, итого 2
$\text{[math]}$
$\text{[math]}$	+1 телепортация, итого 3
$\text{[math]}$	дрон 1 финишировал
$\text{[math]}$	+1 телепортация, итого 4
$\text{[math]}$
$\text{[math]}$	дрон 2 финишировал

Если $k=3$, то гонка происходит следующим образом. На рисунках показаны моменты, когда дроны оказываются в воротах и происходит телепортация.

$\text{[math]}$
$\text{[math]}$	$\text{[math]}$
	2 телепортации
$\text{[math]}$	$\text{[math]}$
	+2 телепортации, итого 4
$\text{[math]}$	$\text{[math]}$
	+2 телепортации, итого 6
$\text{[math]}$	$\text{[math]}$
дрон 1 финишировал	+2 телепортации, итого 8
$\text{[math]}$	$\text{[math]}$
	+1 телепортация, итого 9
$\text{[math]}$	$\text{[math]}$
	+1 телепортация, итого 10
$\text{[math]}$	$\text{[math]}$
дрон 2 финишировал	+1 телепортация, итого 11
$\text{[math]}$	$\text{[math]}$
	дрон 3 финишировал

Примеры

Входные данные

3 3
1 2 3
1 3 6

Выходные данные

0
4
11

Входные данные

3 3
3 2 1
1 3 6

Выходные данные

0
5
13

Входные данные

2 5
2 1
1 3 4 6 7

Выходные данные

0
6

Сдать: для сдачи задач необходимо войти в систему

		Ограничения
Подз.	Баллы	\(n\)	\(m\)	\(t_i, s_i\)	Доп. ограничения	Необх. подзадачи
1	5	\(n = 2\)	\(m \le 50\)	\(t_i,s_i \le 100\,000\)
2	7	\(n \le 50\)	\(m \le 50\)	\(t_i,s_i \le 100\,000\)		У, 1
3	13	\(n \le 1000\)	\(m \le 5\)	\(t_i,s_i \le 100\,000\)		У
4	9	\(n \le 100\,000\)	\(m \le 100\,000\)	\(t_i,s_i \le 100\,000\)	\(s_{i+1} - s_i = s_1\) для всех \(1 \le i < m\)
5	8	\(n \le 100\,000\)	\(m \le 100\,000\)	\(t_i,s_i \le 100\,000\)	все \(t_i\) равны
6	10	\(n \le 100\)	\(m \le 100\,000\)	\(t_i,s_i \le 100\,000\)		У, 1 – 2
7	5	\(n \le 100\,000\)	\(m \le 100\,000\)	\(t_i \le 2\), \(s_i \le 100\,000\)
8	7	\(n \le 100\,000\)	\(m=2\)	\(t_i,s_i \le 100\,000\)
9	6	\(n \le 10\,000\)	\(m \le 100\,000\)	\(t_i,s_i \le 100\,000\)		У, 1 – 3, 6
10	6	\(n \le 50\,000\)	\(m \le 100\,000\)	\(t_i,s_i \le 100\,000\)		У, 1 – 3, 6, 9
11	8	\(n \le 100\,000\)	\(m \le 100\,000\)	\(t_i,s_i \le 100\,000\)		У, 1 – 10
12	8	\(n \le 100\,000\)				У, 1 – 11
13	8	без дополнительных ограничений				У, 1 – 12