Задача №115386. Холмы и ямы
В пустынном городе с холмистым ландшафтом мэрия решила выровнять поверхность дороги, закупив самосвал. Дорога разделена на \(n\) участков, пронумерованных от \(1\) до \(n\) слева направо. Высота поверхности на \(i\)-м участке равна \(a_i\). Если высота \(i\)-го участка больше \(0\), то самосвал должен забрать песок с \(i\)-го участка дороги, а если высота \(i\)-го участка меньше \(0\), то самосвал должен засыпать песком яму на \(i\)-м участке дороги. Гарантируется, что изначальные высоты не равны \(0\).
Когда самосвал находится на \(i\)-м участке дороги, он может либо забрать оттуда \(x\) единиц песка, и тогда высота поверхности на \(i\)-м участке уменьшится на \(x\), либо засыпать туда \(x\) единиц песка (при условии, что у него в кузове сейчас есть хотя бы \(x\) единиц песка), и тогда высота поверхности на \(i\)-м участке дороги увеличится на \(x\).
Самосвал может начать свой путь на любом участке дороги. Перемещение на соседний слева или справа участок дороги занимает \(1\) минуту, при этом временем загрузки и разгрузки песка можно пренебречь. Кузов самосвала имеет бесконечную вместимость и изначально пуст.
Вам нужно найти минимальное время, за которое самосвал сможет выровнять песок так, чтобы высота на каждом участке стала равна \(0\). Обратите внимание, что после всех передвижений в кузове самосвала может остаться песок . Вам нужно решить эту задачу независимо , если оставить только участки с номерами от \(l_i\) до \(r_i\). При этом использовать песок вне отрезка нельзя.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа \(n\) и \(q\) (\(1 \le n, q \le 3 \cdot 10^5\)) — количество участков и количество запросов.
Вторая строка каждого набора входных данных содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(-10^9 \le a_i \le 10^9\), \(a_i \neq 0\)) — изначальная высота на каждом участке.
\(i\)-я из следующих \(q\) строк содержит два целых числа \(l_i\) и \(r_i\) (\(1 \le l_i \le r_i \le n\)) — границы отрезка участков, для которого нужно определить минимальное время.
Гарантируется, что сумма \(n\) по всем наборам входных данных и сумма \(q\) по всем наборам входных данных не превосходит \(3 \cdot 10^5\).
Для каждого запроса выведите минимальное время в минутах, необходимое, чтобы выровнять песок на отрезке \([l_i, r_i]\), или \(-1\), если это невозможно.
В первом наборе входных данных нужно добавить \(179\) единиц песка на единственном участке. Но забрать их неоткуда, поэтому это невозможно.
Во втором наборе входных данных:
-
В первом запросе самосвал может начать путь на втором участке. Он может забрать \(2\) единицы песка, после чего на втором участке высота станет равна \(0\). Затем самосвал может переехать на третий участок. Он может высыпать туда \(1\) единицу песка, после чего на третьем участке высота станет равна \(0\). Затем самосвал может переехать на четвёртый участок. Там он может забрать \(3\) единицы песка, после чего на четвёртом участке высота станет равна \(0\). Суммарно самосвал потратит на перемещения \(2\) минуты.
-
Во втором запросе самосвал может начать путь на четвёртом участке. Он может забрать \(3\) единицы песка, после чего на четвёртом участке высота станет равна \(0\). Затем самосвал может переехать на пятый участок. Он может высыпать туда \(1\) единицу песка, после чего на пятом участке высота станет равна \(0\). Затем самосвал может переехать на четвёртый участок, а потом на третий. Он может высыпать \(1\) единицу песка, после чего на третьем участке высота станет равна \(0\). Затем самосвал может переехать на второй участок. Он может забрать \(2\) единицы песка. Затем он может переехать на первый участок. Он может высыпать \(2\) единицы песка, после чего на первом участке высота станет равна \(0\). Суммарно самосвал потратит на перемещения \(5\) минут.
- В третьем запросе самосвал не сможет сделать высоту на каждом участке равной \(0\).
5 1 1 -179 1 1 5 3 -2 2 -1 3 -1 2 4 1 5 1 3 7 1 1 1 1 -4 1 1 1 1 7 7 2 2 -2 2 -2 1 2 -1 1 7 2 7 3 2 -1000000000 1 1000000000 1 2 1 3
-1 2 5 -1 8 6 6 -1 2