eolymp
bolt
Try our new interface for solving problems
Məsələlər

Önəmli inversiya

Önəmli inversiya

İxtiyari \textbf{x_1, x_2, ..., x_n} ədədlər ardıcıllığına baxaq. Əgər\textit{\textbf{ }}\textbf{j} < \textbf{k} və \textbf{x_j} > \textbf{x_k} olarsa, onda (\textbf{j}, \textbf{k}) indekslər cütü inversiya (sıranın pozulması) adlanır. İxtiyari müsbət \textbf{t }ədədi üçün əgər \textbf{j} < \textbf{k} və \textbf{x_j} > \textbf{x_k} + \textbf{t} şərtləri ödənilirsə, onda (\textbf{j}, \textbf{k}) indekslər cütünü\textbf{ t}-önəmli inversiya adlandırılacaq. \textbf{x}_1, \textbf{x}_2, ..., \textbf{x_n} ardıcıllığında\textit{\textbf{ }}\textbf{t}\textit{\textbf{-}}önəmli inversiyaların sayını hesablayın. \InputFile Birinci sətirdə iki tam\textbf{ n (1 ≤ n ≤ 50000) }və\textbf{ t (0 ≤ t ≤ 10^9)} ədədləri yerləşir. İkinci sətirdə hər biri mütləq qiymətcə \textbf{10^9}-u aşmayan \textbf{x_1, x_2, ..., x_n} tam ədədləri yazılır. \OutputFile \textbf{x_1, x_2, ..., x_n} ardıcıllığında\textit{\textbf{ }}\textbf{t}\textit{-}önəmli inversiyaların sayını çıxışa verin.
Zaman məhdudiyyəti 0.5 saniyə
Yaddaşı istafadə məhdudiyyəti 32 MiB
Giriş verilənləri #1
6 0
1 2 2 9 5 4
Çıxış verilənləri #1
3

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

Müəllif Alexandr Rybak
Mənbə ІІІ (городской) этап Всеукраинской олимпиады школьников по информатике, 2013, г. Киев