Problema D - Colónia de Formigas

O Pedro tem uma colónia de formigas, que consiste em N apartamentos em linha númerados de 0 a N - 1. Cada apartamento contém um conjunto de formigas, sendo que o i-ésimo contém A_i formigas, valor esse que o Pedro desconhece. O seu irmão mais novo Gonçalo está muito curioso sobre a colónia de formigas e decide começar a fazer I perguntas ao seu irmão, sendo a i-ésima: dado um intervalo [L_i, R_i] qual o máximo de formigas num único apartamento desse intervalo de posições. Como o Gonçalo queria muito saber as respostas, o Pedro construiu uns mini-robots para contar formigas, usando os seus conhecimentos adquiridos nas ONI. No entanto, sempre que ele manda k robots investigar a colónia, depois destes completarem a sua missão, são abandonados no meio da colónia. Seja B_i o número de robots abandonados no apartamento i, que no início é 0.

O Pedro pode enviar no máximo K robots investigar a colónia. Assim, sempre que o Pedro manda k dos seus robots investigar a colónia, estes calculam o valor da função maxFormigas(l, r, k), que devolve o máximo de k*A_i + B_i, com i contido no intervalo [l, r] fornecido, mas em contrapartida, adiciona alguns robots à colónia assim que devolve a resposta. Em particular, se k > r-l (se enviar mais robots do que apartamentos no intervalo), um robot é adicionado a cada apartamento em [l, r], caso contrário, os k robots são distribuidos de forma arbitrária pelos apartamentos em [l, r], sendo que nenhum destes fica com mais do que um robot novo. Por outras palavras, aplicamos B_i += 1 a todo o i no intervalo [l, r] se k > r-l ou a k apartamentos arbitrários distintos caso contrário.

Nota que o valor de k é no mínimo 0 (e neste caso nenhum robot é enviado e nenhum robot é perdido) e no máximo K (um inteiro positivo), não existe mais nenhuma restrição a este valor (ou seja, podes assumir que após perder alguns robots, o Pedro pode sempre construir mais para as próximas investigações).

O teu objetivo é ajudar o Pedro a responder às I perguntas do Gonçalo da forma indicada acima, utilizando a função maxFormigas que é executada pelos robots construídos pelo Pedro. Como o Gonçalo é incapaz de se acalmar depois de fazer uma pergunta, só faz uma pergunta nova depois de obter uma resposta. Como o Gonçalo é muito impaciente, o Pedro só pode realizar no máximo Q investigações por pergunta do irmão, ou seja, chamar a função maxFormigas Q vezes.

O Problema

Dado o número de apartamentos N e um conjunto de I intervalos, calcular para cada intervalo o máximo de A usando apenas a função maxFormigas(l, r, k) com k no máximo um dado K e chamando-a no máximo Q vezes por intervalo.

Ficheiros para Download

Podes começar por descarregar os ficheiros correspondentes à tua linguagem (ou um arquivo zip contendo tudo):

Nota que a implementação do avaliador a usar nos testes oficiais será diferente, mas podes esperar o mesmo comportamento. Além disso, é garantido que o avaliador implementa a função maxFormigas em O(r - l).

Implementação

Deves submeter um único ficheiro que implementa duas funções:

• A função iniciar(N, I, K, Q), que recebe um inteiro N, que representa o número de apartamentos, um inteiro I, que representa o número intervalos, um inteiro K, que representa o número máximo de robots por investigação e um inteiro Q, que representa o número máximo de investigações por intervalo. Esta função será invocada uma única vez e antes de qualquer chamada à função pergunta.
• A função pergunta(L, R), que recebe dois inteiros L e R que representam um intervalo perguntado pelo Gonçalo, a função deve retornar a resposta do intervalo.

Para isso deves usar o ficheiro resolver.{c,cpp} que descarregaste, colocando no interior das funções o teu código. Podes acrescentar outras funções, mas devem ficar todas neste ficheiro que é o único que deves submeter.

Funções a implementar:

A tua função deve invocar a seguinte função:

• A função maxFormigas(l, r, k), que recebe três inteiros l, r e k e devolve o máximo de k*A_i + B_i para i no intervalo [l, r].

Nota o seguinte:

• Podes invocar a função maxFormigas na função iniciar, que estará sujeita ao mesmo limite de Q chamadas por intervalo.
• Os valores de l e r devem representar um intervalo válido de 0 a N - 1 e k deve ser no máximo K e no mínimo 0, se alguma chamada não respeitar estas condições, o teu código terá o resultado de Wrong Answer.
• Se excederes as Q chamadas para um intervalo (ou seja, durante uma execução de pergunta ou iniciar), o teu código terá o resultado de Wrong Answer.

Funções do avaliador:

A tua função não deve ler nem escrever para os canais de entrada/saída padrão.

Exemplo

Vamos supor que há N = 5 apartamentos e que a colónia é representada pelo seguinte array: [2 1 6 3 1].

Uma possível execução seria a seguinte (com a ordem das chamadas a ser de cima para baixo):

Restrições

Os valores de K, de robots a enviar numa investigação, assim como os valores de Q, máximo investigações por intervalo, são dados na secção seguinte.

Avaliação e Casos de Teste

Os casos de teste deste problema estarão agrupados em conjuntos de testes. Ao contrário dos restantes problemas, para obter pontuação é necessário acertar todos os casos de teste de um grupo de casos, nesse caso terão a pontuação completa relativa a esse grupo. Se falharem um ou mais casos de um grupo, a pontuação atribuída relativa a esse grupo será nula.

Cada grupo tem um número de pontos associado e um conjunto de restrições adicionais. Os grupos são os seguintes:

Testes no vosso computador

É disponibilizado um avaliador exemplo em cada linguagem (avaliador.{c,cpp}) que pode ser utilizado para testar a tua submissão. Está ainda disponível um ficheiro auxiliar (avaliador.h). Este avaliador não corresponde ao utilizado pelo sistema de avaliação.

Este avaliador começa por receber como input um inteiro N, um inteiro I, um inteiro K e um inteiro Q, correspondendo, respetivamente, ao número de apartamentos, ao número de perguntas, número máximo de robots a enviar numa investigação e ao número máximo investigações por intervalo. Segue-se uma linha com N inteiros não negativos, representando os valores de A_i. Seguem-se I linhas, uma para cada pergunta, cada uma com 2 inteiros L e R, separados por espaços, representando uma pergunta a responder.

O avaliador irá automaticamente invocar a função iniciar(N,I,K,Q), por vocês implementada, uma vez, e invocará seguidamente a função pergunta(L, R) I vezes, uma para cada intervalo. O avaliador indicará se a resposta é considerada correta ou não.

Disponibilizamos um ficheiro de teste:

• input.txt que contém o caso de exemplo referido acima.

Um exemplo de teste na tua máquina (supondo que tens os compiladores oficiais instalados) seria o seguinte: