Distinct Values Subarrays II.

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 256M

Authors:

Problem types

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Rust, Scala, ~~Swift~~, VB, Zig

Dada un arreglo de $n$ ~n~ enteros, su tarea consiste en calcular el número de subarreglos que tienen como máximo $k$ ~k~ valores distintos.

La primera línea de entrada tiene dos enteros: $n$ ~n~ y $k$ ~k~ $(1 \leq k \leq n \leq 2 \cdot 10^5)$ ~(1 \leq k \leq n \leq 2 \cdot 10^5)~.
La siguiente línea tiene $n$ ~n~ enteros $x_1,x_2,\dots,x_n$ ~x_1,x_2,\dots,x_n~ $(1 \leq x_i \leq 10^9)$ ~(1 \leq x_i \leq 10^9)~: el contenido del arreglo.

Imprime un entero: el número de subarreglos.

5 2
1 2 3 1 1

Nota: Se garantiza que $n \leq 100$ ~n \leq 100~ para el 20% de los casos.

Comments

There are no comments at the moment.