ŠIOM — Unikumas

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Unikumas

Šiame uždavinyje jums duota $N$ sveikųjų skaičių seka $a_1,a_2,...,a_N$ bei vienas natūralusis skaičius $k$ . Jūsų užduotis - kiekvienam duotos sekos $k$ ilgio intervalui atsakyti, kiek tame intervale yra skirtingų skaičių.

Pavyzdžiui, jei jums duotas sąrašas $[1,2,1,3,3,3,1]$ ir $k=3$ , tai galimi $k$ ilgio intervalai yra šie: $[1,2,1]$ , $[2,1,3]$ , $[1,3,3]$ , $[3,3,3]$ , $[3,3,1]$ . Jie atitinkamai turi po tiek skirtingų skaičių: $2,3,2,1,2$ .

Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai $N$ ir $k$ ( $1\\leqk\\leqN\\leq2\\cdotp10^5$ ).

Antroje eilutėje pateikta $N$ tarpais atskirtų sveikųjų skaičių $a_1,a_2,...,a_N$ ( $1\\leqa_i\\leq10^9$ ).

Rezultatai

Jūsų programa turi atspausdinti $n-k+1$ tarpais atskirtų sveikųjų skaičių $c_1,c_2,...,c_{n-k+1}$ . Skaičius $c_i$ nurodo, kiek skirtingų skaičių yra intervale $a_i,a_{i+1},...,a_{i+k-1}$ .

Pavyzdžiai

Pradiniai duomenys	Rezultatai
7 3 1 2 1 3 3 3 1	2 3 2 1 2

Šeštadieninė informatikos olimpiadininkų mokykla

Unikumas

Pradiniai duomenys

Rezultatai

Pavyzdžiai