团体入座

【题目描述】

小灰灰管理着一排 $N$ 个座位，从左到右编号为 $1,2,\ldots,N$，初始全部空着．接下来会发生 $q$ 次操作．

一组观众到来时，这组的 $k$ 人需要坐在连续的 $k$ 个空座位上．如果存在这样的座位，他们会选择与原先已经在座的观众尽量远的位置．具体来说：

对于一个可选座位区间 $[l,l+k-1]$，它的距离是该区间内的座位与原先已有人坐的座位之间，所有编号差的绝对值的最小值．选择距离最大的区间；如果有多个，选择左端点最小的区间．同组新到观众之间的距离不参与本次计算．

如果当前没有任何观众，就选择最左边的 $k$ 个座位．如果找不到连续的 $k$ 个空座位，这组观众不会入座，座位状态不变．

还有一些操作会指定一个仍在座的组，让这一整组观众离开，他们占据的座位全部变为空位．每个组用它到来的操作编号标识；操作编号从 $1$ 开始，入座失败和离开操作也占用操作编号．

请对每次有观众到来的操作，输出他们最终占据的区间的左端点；如果无法入座，输出 -1．

【输入描述】

第一行输入两个整数 $N,q$，分别表示座位数和操作次数．

接下来 $q$ 行，每行描述一次操作：

• 1 k：一组 $k$ 人到来．
• 2 t：在第 $t$ 次操作中入座的整组观众离开．

对于第 $i$ 次操作中的 2 t，保证 $1\le t<i$，第 $t$ 次操作为成功入座的操作，且该组在此之前尚未离开．

【输出描述】

对于每次类型为 1 的操作，输出一行一个整数，为入座区间左端点或 -1．类型为 2 的操作不产生输出．

【样例 1】

【样例 1 输入】

10 7
1 2
1 2
1 2
1 3
2 3
1 3
2 1

【样例 1 输出】

1
9
5
-1
4

【样例 1 解释】

• 第一次无人已在座，因此选择 $[1,2]$．
• 第二次选择 $[9,10]$，它与原先观众的最小距离为 $7$．
• 第三次选择 $[5,6]$，它与原先观众的最小距离为 $3$．
• 第四次剩余空位为 $[3,4]$ 和 $[7,8]$，虽然总共还有四个空位，但不存在连续三个空位，因此入座失败．
• 第五次让第三次操作入座的观众离开，空位成为 $[3,8]$．
• 第六次选择 $[4,6]$．它与 $[5,7]$ 的距离都为 $2$，取左端点较小的 $[4,6]$．
• 第七次让第一次操作入座的观众离开，不输出内容．

【样例 2】

【样例 2 输入】

5 4
1 5
1 1
2 1
1 2

【样例 2 输出】

1
-1
1

【样例 2 解释】

第一组占满全部座位，第二组入座失败．第一组离开后，座位全部空出，第四次操作的观众选择最左边的两个座位．

【数据规模与约定】

对于所有数据，$1\le N\le10^9$，$1\le q\le2\times10^5$．每次类型为 1 的操作满足 $1\le k\le N$．

本题采用捆绑测试．只有通过一个子任务的全部测试点，才能获得该子任务的分数．

子任务编号	分数	附加限制
1	10	$N,q\le2000$
2	20	$q\le3000$
3		存在一个正整数 $K$，所有类型为 1 的操作均满足 $k=K$
4	15	所有操作的类型均为 1
5	35	无

【下发样例】

• Data/sample1.in 与 Data/sample1.ans：样例 1．
• Data/sample2.in 与 Data/sample2.ans：样例 2．
• Data/sample3.in 与 Data/sample3.ans：满足子任务 1 的限制．
• Data/sample4.in 与 Data/sample4.ans：满足子任务 2 的限制．
• Data/sample5.in 与 Data/sample5.ans：满足子任务 3 的限制．
• Data/sample6.in 与 Data/sample6.ans：满足子任务 4 的限制．
• Data/sample7.in 与 Data/sample7.ans：该样例无特殊限制．
• Data/sample8.in 与 Data/sample8.ans：该样例无特殊限制．

点击下载本题选手目录