UVA12419 Heap Manager

在这个问题中，你需要模拟一个内存管理器。 你有一个大小为 $n$ 的内存，其地址范围为 $0..n-1$。每个内存单元不是空闲就是被占用。如果有 $k$ 个连续的空闲内存单元 $a,a+1,a+2,...,a+k-1$，我们称其为一个长度为 $k$ 的空闲内存片。 有时候，会有一些进程来访问内存。我们可以用 $(a,b,c)$ 表示在 $a$ 刻，这个进程要申请一个长度为 $b$ 的空闲内存片，并且占用 $c$ 刻。 我们假设 $t'$ 时某个内存单元被某个进程占用，那么 $t'+c$ 刻这个内存单元将被释放。 首先你需要对所有内存申请按 $a$ 从小到大的顺序排列，并放置一个空的候选队列，然后进行以下操作： - 如果在 $a$ 时刻有长度为 $b$ 的空闲内存片，同意此申请，如果有多个符合要求的，取地址下标最小的那一个 - 如果在 $a$ 时刻没有长度为 $b$ 的空闲内存片，这个访问将被放入候选队列，如果有一个空闲内存片符合候选队列的队头，那么立刻给其使用。 - 注意，只有当候选队列的第一个没有符合条件的空闲随便或者候选队列为空时，才会处理下一个请求。

无

无

$10\le n\le10^9$ $0\le t\le 1$ $0\le b\le n$ $0\le a,c\le 10^9$ 保证单个样例不超过 $200001$ 行，保证输入文件不超过 10MB。 翻译 by [279700](https://www.luogu.com.cn/user/279700)