P6928 [ICPC 2016 WF] What Really Happened on Mars?

你有 $t$ 个进程和 $r$ 个资源，每个进程包含其起始时间与**基础优先级**（保证两两不同），以及若干条指令。指令有以下三种： - `compute`：进行计算，消耗 $1$ 微秒。 - `lock k`：锁定编号为 $k$ 的资源，不耗时。 - `unlock k`：解锁编号为 $k$ 的资源，不耗时。 在进程锁定资源后，这个进程就拥有了这个资源直到这个进程将它解锁。保证任意进程只会解锁最近锁定的资源，不会锁定自身拥有的资源，且在进程结束时不会拥有任何资源。 每个资源有一个固定的属性**最高优先级**，即包含锁定该资源指令的所有进程的最高**基础优先级**。 有一个处理器处理这些进程。处理器有一个时钟初始为 $0$，然后重复执行下列步骤： 1. 找出所有正在运行的进程。如果进程开始的时间不大于处理器的时钟且该进程的指令未运行完毕，那么称这个进程正在运行。 2. 决定当前所有正在运行的进程的优先级，以及哪些正在运行的进程会被阻塞。进程 $T$ 会被阻塞当且仅当： - 进程 $T$ 的下一条指令是锁定资源 $k$。 - 资源 $k$ 已经被其他进程拥有，或存在另一个进程拥有某个资源 $\ell$，$\ell$ 的**最高优先级**大于等于 $T$ 的**当前优先级**。 此时我们称进程 $T$ 被所有拥有资源 $k$ 或满足条件的资源 $\ell$ 的进程阻塞。定义 $T$ 的**当前优先级**为所有它阻塞的进程的**当前优先级**与它本身的**基础优先级**的最大值。 3. 执行**当前优先级**最高且没有被阻塞的进程的下一条指令。如果不存在这样的进程或者执行的指令是 `compute`，则将时钟加 $1$ 微秒。 你需要求所有进程的结束时间。可以证明所有进程一定会结束。

第一行两个整数 $t,r$ 表示进程和资源个数。 接下来 $t$ 行每行描述一个进程，格式如下： - 三个整数 $s,b,a$，表示进程起始时间、基础优先级、指令条数。 - 接下来 $a$ 个字符串，每个字符串表示一条指令。字符串形如 `Cn` 表示连续 $n$ 个 `compute` 指令（**相互独立**），`Lk` 表示锁定资源 $k$，`Rk` 表示解锁资源 `k`。

$t$ 行每行一个整数表示进程执行完毕的时间。 数据范围：$1 \le t,r \le 20,s \le 10^4,1 \le b \le t$ 且互不相同，$a \le 100$，`Cn` 中 $n \le 100$，`Lk,Rk` 中 $1 \le k \le r$。 Translated by pokefunc (uid=188716)

Time limit: 1000 ms, Memory limit: 1048576 kB. International Collegiate Programming Contest (ACM-ICPC) World Finals 2016