Подразделы

Другие разделы

Дата и время

13/03/2025 13:22:09

Авторизация

2458. Задача торговца

Задача торговца

Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Вдоль длинной дороги расположены несколько городов, пронумерованных от 1 до

$n$ . В каждом городе можно купить или продать некоторый товар. Этот товар имеет большой размер, поэтому торговец может везти с собой не более одной единицы товара. В

$i$ -м городе товар можно купить за

$p_i$ золотых, а продать за

$(p_i\ -\ 1)$ золотых.

Определите максимальную прибыль, которую может получить торговец при путешествии из города

$s$ в город

$t$ .

Первая строка ввода содержит одно целое число

$n$ (

$2\ ≤\ n\ ≤\ 10^6$ ) – количество городов. Вторая строка ввода содержит

$n$ целых чисел

$p_i$ в диапазоне от 1 до

$10^6$ – цена товара в каждом городе. Третья строка ввода содержит одно целое число

$m$ (

$1\ ≤\ m\ ≤\ 10^5$ ) – количество запросов на вычисление прибыли. Далее следует

$n$ строк, содержащих по два целых числа

$s$ и

$t$ (

$1\ ≤\ s,\ t\ ≤\ n$ ,

$s\ ≠\ t$ ) – номера начального и конечного города путешествия.

Для каждого запроса вывести на соответствующей строке одно целое число – максимальную прибыль, которую может получить торговец при путешествии из города