Solução Informática - Nivel Intermediário - Semana 6

Solução por Leonardo Paes

Conhecimento prévio necessário:

• Soma de Prefixos

Para resolver esse problema, utilizaremos a ideia de Soma de Prefixos.

Para que a tripla $x \leq y \leq z$ forme um triângulo não degenerado, é necessário e suficiente que ela satisfaça a condição $x + y < z$, devido à desigualdade triangular.

Vamos calcular para todo $s = x + y$ quantas maneiras existem para escolher $(x, y)$. Para isso, tentaremos todos os $x$ e adicionaremos 1 no segmento $[x + B; x + C]$ de maneira offline usando somas de prefixo.

Calculando somas de prefixo mais uma vez, podemos encontrar em $O(1)$ quantas maneiras de escolher um par $(x, y)$ existem de modo que sua $x+y$ seja maior que $z$.

Tentando todo $z$, calculamos a resposta dele.

Complexidade total - $O (C)$.

Código de exemplo: