Memória sob medida
Uma memória tem unidades consecutivas, com endereços de 1 a , inicialmente livres. Um bloco ocupa um intervalo de unidades consecutivas. Processe operações, numeradas de 1 a :
A s: reserve unidades livres consecutivas. Escolha o menor endereço inicial possível. Se conseguir, o identificador do novo bloco é o número desta operação; caso contrário, nenhum bloco é criado. Imprima o endereço inicial ou-1em caso de falha.D id: libere o bloco de identificadorid. Se ele não estiver ativo, não faça nada. Esta operação não produz saída.R id s: tente mudar o tamanho de um bloco ativo para , conforme as regras abaixo. Seidnão estiver ativo, imprima-1.
Para redimensionar um bloco ativo:
- Se o novo tamanho é menor ou igual ao atual, mantenha seu endereço inicial e libere o excesso à direita, se houver.
- Se o novo tamanho é maior e há espaço livre suficiente imediatamente à direita, aumente o bloco sem mudar seu endereço inicial. Essa opção tem prioridade sobre qualquer outra posição livre.
- Caso contrário, procure um novo intervalo livre de tamanho , com o menor endereço inicial possível. O bloco antigo continua ocupado durante essa busca. Se encontrar, reserve o novo intervalo e só então libere o antigo. O identificador do bloco não muda.
- Se a busca falhar, mantenha o bloco antigo sem qualquer alteração.
Uma operação R bem-sucedida imprime o endereço inicial resultante; uma falha imprime -1. Não é preciso simular o conteúdo armazenado, apenas a ocupação da memória.
Input
A primeira linha contém e . As próximas linhas contêm as operações no formato acima.
- e ;
Output
Para cada operação A ou R, imprima uma linha com o resultado solicitado. Não imprima nada para D.
Samples
Sample 1
Input
10 9 A 3 A 3 R 1 5 D 2 R 1 5 A 2 R 1 3 R 6 4 A 2
Output
1 4 -1 1 6 1 6 4
A primeira tentativa de aumentar o bloco 1 falha e preserva suas três unidades. Após liberar o bloco 2, o bloco 1 pode crescer no lugar. Ao final, o intervalo livre que começa em 4 recebe a última alocação.
Sample 2
Input
12 5 A 3 A 2 R 1 4 R 1 5 A 3
Output
1 4 6 6 1
O bloco 2 impede o crescimento do bloco 1 no lugar. O bloco 1 é transferido para as unidades 6 a 9, preservando seu identificador; depois cresce até a unidade 10. A última alocação aproveita as unidades 1 a 3 liberadas pela transferência.