Олимпиадный тренинг

Задача . F. Поликарп и банкомат


Задача

Темы: Бинарный поиск два указателя Структуры данных *1800

Поликарп начал работать в банке. Ему назначили следить за банкоматом. В банкомате изначально есть \(s\) рублей.

К нему выстроились очередь из \(n\) студентов. Каждый студент хочет либо снять некоторое количество денег, либо внести на счёт. Если \(a_i\) положительное, то студент зачисляет через банкомат такое количество денег. В противном случае — снимает \(|a_i|\) рублей.

В начале в банкомате \(s\) рублей и он отключён. Поликарп пропускает произвольное количество студентов. В какой-то момент времени Поликарп включает банкомат. Затем банкомат начинает обcлуживать оставшихся студентов по очереди. Если в какой-то момент времени в банкомате меньше рублей, чем хочет снять студент, тогда студент не обслуживается и Поликарп выключает банкомат и больше его никогда не включает.

Более формально, студенты, которые будут обслужены образуют непрерывную подпоследовательность.

Поликарп хочет, чтобы банкомат обслужил наибольшее количество студентов. Помогите ему в этом деле. Выведите номера первого и последнего студента или определите, что он не сможет никого обслужить.

Иными словами, найдите такой максимальный по длине непрерывный подотрезок студентов, что, начав с суммы \(s\) в банкомате, все эти студенты будут обслужены. Банкомат обслуживает студентов последовательно в порядке очереди.

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

В первой строке входных данных записано целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных в тесте.

Каждый набор входных данных состоит из двух строк. В первой из них записаны целые числа \(n\) и \(s\) (\(1 \le n \le 2\cdot10^5\); \(0 \le s \le 10^9\)) — длина массива \(a\) и начальное количество рублей в банкомате. Во второй записаны \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(-10^9 \le a_i \le 10^9\)) — элементы массива \(a\). Заметьте, что \(a_i\) может быть равен нулю.

Гарантируется, что сумма значений \(n\) по всем наборам входных данных в тесте не превосходит \(2\cdot10^5\).

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

Выведите \(t\) строк, каждая из строк должна содержать ответ на соответствующий набор входных данных: если ответ существует выведите номера первого и последнего обслуженного студента. Если решения не существует, то в строку выведите -1.

Если есть несколько возможных ответов, выведите любой.

Примечание

В первом наборе входных данных единственным правильным ответом является 2 4, так как при обслуживании студентов количество рублей в банкомате не становится отрицательным, и это максимальное количество студентов, которое возможно обслужить.

Во втором наборе входных данных ответ -1, так как для любого студента в банкомате недостаточно денег.

В третьем наборе входных данных ответ может быть как 1 2, так и 4 5.


Примеры
№Входные данныеВыходные данные
1 3
4 10
-16 2 -6 8
3 1000
-100000 -100000 -100000
6 0
2 6 -164 1 -1 -6543 
2 4
-1
1 2

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет