Encima de la Mediana


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal

El Granjero Juan (GJ) ha alineado sus N (1 \leq N \leq 100 000) vacas en una fila para medir sus alturas, la vaca i tiene altura H_i (1 \leq H_i \leq 1 000 000 000) nanómetros -- ¡GJ cree en las mediciones precisas! Él quiere tomar una fotografía de una subsecuencia contigua de vacas para enviarla a una competencia de fotografía bovina en la feria del condado.

La feria tiene una regla muy extraña con respecto a las fotos enviadas: se acepta una fotografía si las alturas del grupo de vacas en ella tiene una mediana que sea al menos de un límite X (1 \leq X \leq 1 000 000 000).

Para propósitos de este problema, definimos la mediana de un arreglo A [0...K] como A [techo (K/2)] después que A esté ordenado, donde techo (K/2) da K/2 redondeado al entero más cercano por encima (o K/2 mismo, si K/2 es un entero). Por ejemplo, la mediana de {7, 3, 2, 6} es 6, y la mediana de {5, 4, 8} es 5.

Por favor, ayude a GJ a contar el número de subsecuencias contiguas diferentes de sus vacas que él podría enviar potencialmente al concurso de fotografía.

Entrada

• Línea 1: Dos enteros separados por espacio: N y X.

• Líneas 2…N+1: La línea i+1 contiene un solo entero H_i.

Ejemplo de Entrada

4 6
10
5
6
2

Detalles de la Entrada

Las cuatro vacas del Granjero Juan tienen alturas 10, 5, 6, 2. Queremos saber cuántas subsecuencias contiguas tienen mediana de al menos 6.

Salida

• Línea 1: El número de subsecuencias de las vacas de GJ que tienen mediana de al menos X. Note que este número puede no entrar en un entero de 32 bits.

Ejemplo de Salida

7

Detalles de la Salida

Hay 10 posibilidades de subsecuencias contiguas a considerar. De estas únicamente 7 tienen mediana de al menos 6. Ellas son {10}, {6}, {10, 5}, {5, 6}, {6, 2}, {10, 5, 6}, {10, 5, 6, 2}.


Comments

There are no comments at the moment.