P5763 [NOI1999] Memory Allocation

Memory is one of the important resources of a computer. During program execution, memory must be allocated. A classic memory allocation process works as follows: 1. Memory is divided into memory units as the basic unit. Each memory unit is identified by a fixed integer, called its address. Addresses start from $0$ and are arranged consecutively. Memory units with adjacent addresses are considered logically consecutive. We call the $s$ consecutive memory units starting from address $i$ an address segment with starting address $i$ and length $s$. 2. During execution, several processes need to occupy memory. For each process, there is a request time $T$, a required number of memory units $M$, and a running time $P$. During the running time $P$ (i.e., starting at time $T$ and ending at time $T+P$), these $M$ occupied memory units cannot be used by other processes. 3. Suppose that at time $T$ a process requests $M$ units and has running time $P$. Then: $\qquad$ 1) If at time $T$ there exists a free address segment of length $M$ in memory, the system allocates these $M$ free units to the process. If there are multiple free address segments of length $M$, the system allocates the one with the smallest starting address to the process. $\qquad$ 2) If at time $T$ there is no free address segment of length $M$, the process is put into a waiting queue. For the process at the head of the waiting queue, as long as at any moment there exists a free address segment of length $M$, the system immediately removes it from the queue and allocates memory units to it. Note that during the memory allocation procedure, the process at the head of the waiting queue has the highest priority. Other processes in the queue cannot be processed before the head process. Now you are given a sequence of data describing processes. Please write a program to simulate the system's memory allocation process.

The first line contains an integer $N$, which is the total number of memory units (i.e., the address range is from $0$ to $N-1$). Starting from the second line, each line describes a process with three integers $T, M, P$ ($M \le N$). **The data are already sorted in increasing order of $T$.** The last line is `0 0 0`, indicating the end. The input file has at most $10000$ lines, and all data are less than $10^9$. Adjacent items on the same line in the input file are separated by one or more spaces.

There are two lines in total. The first line is the time when all processes have finished running. The second line is the total number of processes that have ever been put into the waiting queue.

Translated by ChatGPT 5