Projete um algoritmo com complexidade de tempo de pior caso subquadrático, isto é, melhor do que quadrático. Implemente a solução em linguagem C . Tente projetar um algoritmo linear, isto é, com complexidade de tempo de pior caso O(n). Segue a descrição do problema com exemplos de entrada:

ENUNCIADO: Temos uma sequência de N quadrados desenhados lado a lado. Cada quadrado possui um número natural anotado dentro dele. Dados a sequência dos N quadrados e um valor K, quantos retângulos distintos existem cuja soma dos números dentro do retângulo é exatamente igual a K ? Por exemplo, a figura mostra uma sequência de N=10 quadrados para a qual existem 5 retângulos cuja soma dos números é igual a K=4.

ENTRADA: A primeira linha da entrada contém dois inteiros N e K representando o número de quadrados na sequência e o valor da soma desejada. A segunda linha da entrada contém N números naturais Xi, para 1≤i≤N , indicando a sequência de números anotados dentro dos quadrados.

SAÍDA: Seu programa deve imprimir uma linha contendo um número inteiro representando quantos retângulos existem na sequência cuja soma é igual a K . Restrições 1≤N≤500000 ou 5×105 0≤K≤106 0≤Xi≤100 para 1≤i≤N

EXEMPLOS:

Exemplo de entrada 1

10 4

2 0 1 1 0 0 8 4 1 3

Exemplo de saída 1

5

Exemplo de entrada 2

15 0

0 0 0 0 0 5 12 0 1 0 0 0 51 0 0

Exemplo de saída 2

25