Memory Manager
Time limit2sMemory limit1024 MB
Process allocate and free requests over N memory cells; each allocation of K cells must land in the leftmost valid block whose preceding cell is occupied, or be rejected.
- Level
Medium7 of 10
- Topics
- Greedy, Intervals, Implementation, Sorting
- Solved
- No attempts yet
Problem
Petya was asked to write a memory manager for the new standard library of the H++ language. The manager has an array of N consecutive memory cells, numbered from 1 to N. The manager's job is to process applications' requests to allocate and free memory.
An allocation request has a single parameter K. Such a request means the application asks to be allocated K consecutive memory cells. If the manager has at least one free block of K consecutive cells, then in response to the request it must allocate such a block. The cell immediately before the first cell of the block being allocated must not be free. After that the allocated cells become occupied and cannot be used for allocation until they are freed. If there is no block of K consecutive free cells, the request is rejected.
A free request has a single parameter T. Such a request means the manager must free the memory that was allocated earlier while processing the request with serial number T. Requests are numbered starting from one. It is guaranteed that the request with number T is an allocation request, and that no free has been applied to it yet. Freed cells can be used again for allocation. If the request with number T was rejected, the current free request is ignored.
You must write a memory manager that satisfies the criteria above.
Input
The first line of the input file contains the numbers N and M: the number of memory cells and the number of requests, respectively (1 ≤ N ≤ 231 – 1; 1 ≤ M ≤ 105). Each of the following M lines contains a single number: the (i+1)-th line of the input file (1 ≤ i ≤ M) contains either a positive number K if the i-th request is an allocation request with parameter K (1 ≤ K ≤ N), or a negative number –T if the i-th request is a free request with parameter T (1 ≤ T < i).
Output
For each memory allocation request, print the result of processing that request to the output file: for successful requests print the number of the first memory cell in the allocated block, for rejected requests print –1. The results must be printed in the order in which the requests appear in the input file.