eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Существенные инверсии

Существенные инверсии

Рассмотрим произвольную последовательность чисел \textbf{x_1}, \textbf{x_2}, ..., \textbf{x_n}. Пару индексов \textbf{(j, k)} называют \textit{инверсией (нарушением порядка)}, если \textbf{j} < \textbf{k} и \textbf{x_j} > \textbf{x_k}. Для произвольного неотрицательного числа \textbf{t} пару индексов \textbf{(j, k)} назовем \textbf{t}-\textit{существенной инверсией}, если \textbf{j} < \textbf{k} и \textbf{x_j} > \textbf{x_\{k \}+ t}. Подсчитайте количество \textbf{t}-\textit{существенных инверсий} в последовательности \textbf{x_1}, \textbf{x_2}, ..., \textbf{x_n}. \textbf{Входные даннные} Первая строка содержит два целых числа \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{50000}) и \textbf{t} (\textbf{0} ≤ \textbf{t} ≤ \textbf{10^9}). Во второй строке записаны целые числа \textbf{x_1}, \textbf{x_2}, ..., \textbf{x_n}, по модулю не превосходящие \textbf{10^9}. \textbf{Выходные даннные} Вывести количество \textbf{t}-существенных инверсий в последовательности \textbf{x_1}, \textbf{x_2}, ..., \textbf{x_n}.
Лимит времени 0.5 секунд
Лимит использования памяти 32 MiB
Входные данные #1
6 0
1 2 2 9 5 4
Выходные данные #1
3

Объяснение: В примере 1 инверсии такие: (4, 5), (4, 6) и (5, 6). Все эти инверсии — 0-существенные. В примере 2 инверсии следующие: (3, 4) і (3, 5). Однако x3 ≤ x5 + 2, то есть инверсия (3, 5) не является 2-существенной. Такой будет только пара (3, 4).

Автор Александр Рыбак
Источник ІІІ (городской) этап Всеукраинской олимпиады школьников по информатике, 2013, г. Киев