As finanças mantêm um histórico de N dias de atividade de uma empresa. No dia i a empresa reportou um lucro de Si, um inteiro que pode ser positivo, negativo ou zero. Para detetar automaticamente se houve alguma fraude fiscal, as finanças procuram certos padrões nos valores de lucro e por isso precisam de um programa que calcule informação específica sobre estes dados.
É dado um par de inteiros L e R, tais que L ≤ R. Um intervalo de dias tem um valor suspeito se a soma dos lucros nesse intervalo está entre L e R. Mais formalmente, dado um intervalo (a, b), onde a ≤ b, este intervalo é suspeito se L ≤ Sa + Sa + 1 + ... + Sb ≤ R.
Determina o número de intervalos suspeitos.
Se N = 6, L = 2, R = 3 e tivermos os seguintes lucros:
Então temos os seguintes intervalos cuja soma está entre 2 e 3: (1, 2), cuja soma é 2; (4, 5), cuja soma é 3; (5, 5), cuja soma é 2; (5, 6), cuja soma é 3. No total há 4 intervalos suspeitos.
São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:
| 1 ≤ N ≤ 100 000 | Número de dias | |
| 1 ≤ L ≤ R ≤ 1 000 000 | Intervalos suspeitos | |
| -1 000 000 ≤ Si ≤ 1 000 000 | Valores de lucro |
Os casos de teste desta parte do problema estão organizados em três grupos:
| Grupo | Número de Pontos | Restrições adicionais |
|---|---|---|
| 1 | 10 | N ≤ 1 000 |
| 2 | 20 | L = R |
| 3 | 20 |
Determina o tamanho do maior conjunto possível de intervalos suspeitos disjuntos.
Se N = 6, L = 2, R = 3 e tivermos os seguintes lucros:
Então o seguinte conjunto tem 2 intervalos suspeitos disjuntos: {(1, 2), (4, 5)}. Há outros conjuntos possíveis com 2 intervalos suspeitos disjuntos, mas não há nenhum com mais de 2, logo 2 é a resposta para este caso.
São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:
| 1 ≤ N ≤ 100 000 | Número de dias | |
| 1 ≤ L ≤ R ≤ 1 000 000 | Intervalos suspeitos | |
| -1 000 000 ≤ Si ≤ 1 000 000 | Valores de lucro |
Os casos de teste desta parte do problema estão organizados em três grupos:
| Grupo | Número de Pontos | Restrições adicionais |
|---|---|---|
| 4 | 10 | N ≤ 1 000 |
| 5 | 20 | L = R |
| 6 | 20 |
Os casos de teste do problema estão organizados em 3 grupos com restrições adicionais diferentes:
| Grupo | Número de Pontos | Parte | Restrições adicionais |
|---|---|---|---|
| 1 | 10 | Parte I | N ≤ 1 000 |
| 2 | 20 | Parte I | L = R |
| 3 | 20 | Parte I | |
| 4 | 10 | Parte II | N ≤ 1 000 |
| 5 | 20 | Parte II | L = R |
| 6 | 20 | Parte II |
A primeira linha contém um inteiro P, que representa a parte que o caso de teste representa. Se for 1, então o caso de teste refere-se à Parte I, se for 2 então refere-se à Parte II.
Segue-se uma linha com três inteiros separados por espaços, primeiro N, representando o número de dias, seguido de L e R, os valores para intervalos suspeitos.
Segue-se uma linha, contendo N inteiros separados por espaços, representando os valores de S.
O output deve conter uma única linha com um inteiro, o número de intervalos suspeitos.
Nota: Este valor pode ser superior a 232.
O output deve conter uma única linha com um inteiro, o tamanho do maior conjunto de intervalos suspeitos disjuntos.
1 6 2 3 1 1 -5 1 2 1
4
Este exemplo corresponde ao exemplo mencionado na Parte I do enunciado.
2 6 2 3 1 1 -5 1 2 1
2
Este exemplo corresponde ao exemplo mencionado na Parte II do enunciado.