Fişierul intrare/ieşire:subsiruri3.in, subsiruri3.outSursăONIS 2014, Runda 4
AutorTudose Vlad AndreiAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test8 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Subsiruri 3

Aurel are un sir de N numere intregi x1, x2, …, xN. El vrea sa afle in cate moduri poate alege un subsir xi1, xi2, …, xiT cu proprietatea ca 0 ≤ xij - xij-1 ≤ K pentru j = 2 … T. Ajutati-l pe Aurel sa raspunda la aceasta intrebare.

Date de intrare

Fişierul de intrare subsiruri3.in va contine pe prima linie T, numarul de teste. Fiecare test va avea pe prima sa line doua numere naturale, N si K, avand semnificatia din enunt. Urmatoarea linie contine N numere intregi, separate printr-un spatiu, reprezentand sirul lui Aurel.

Date de ieşire

În fişierul de ieşire subsiruri3.out se vor afisa T linii, pe linia i aflandu-se numarul de subsiruri cu proprietatea din enunt pentru testul i, modulo 666013.

Restricţii

  • 1 ≤ T ≤ 5
  • 1 ≤ N ≤ 106
  • 0 ≤ K ≤ 109
  • 0 ≤ xi ≤ 109 pentru i = 1 … N
  • Se numeste subsir al sirului X = (x1, x2, …, xN), un sir Y = (xi1, xi2, …, xiT) cu proprietatea 1 ≤ i1 < i2 < … < iT ≤ N

Exemplu

subsiruri3.insubsiruri3.out
1
4 2
6 2 8 9
7

Explicaţie

Cele 7 subsiruri sunt: {6}, {2}, {8}, {9}, {6, 8}, {6, 8, 9}, {8, 9}.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content