← 返回题目列表

Codeforces · 46/D

D. 停车场

中文机器翻译题面 查看原题

如今,在城市成功停车变得越来越困难。让我们想象一段 L 米长的街道,沿途有一个停车场。驾驶员应将车辆严格平行于街道右侧的人行道停放(请记住,在该国,任务的作者来自右侧驾驶!)。每个司机在停车时都希望给自己留出一些额外的空间来自由移动车辆,所以司机会寻找一个与后车距离不小于b米,与前车距离不小于f米的地方(如果后面没有车,则可以将车停在停车场段边缘;前面没有车时也是如此)。让我们引入沿着人行道的坐标轴。让停车场从0点开始,到L点结束。司机沿着坐标增加的方向行驶,寻找最早可以停车的地方(坐标最小的)。如果没有这样的地方,司机就会继续开车寻找他完美的宁静避风港。有时,一些汽车离开街道,腾出一些停车位。考虑到街道上永远不会同时有两辆行驶的汽车,编写一个程序,可以使用驾驶员的数据,进入街道希望在那里停车,以及驾驶员离开街道的数据,对过程进行建模并确定每辆车的停车位。

输入

第一行包含三个整数 L, b è f (10 ≤ L ≤ 100000, 1 ≤ b, f ≤ 100)。第二行包含一个整数 n (1 ≤ n ≤ 100),表示程序收到的请求数。每个请求都在一行上进行描述,并由两个数字给出。第一个数字代表请求类型。如果请求类型等于 1,则在这种情况下,第二个数字表示进入街道寻找停车位的汽车的长度(以米为单位)。如果请求类型等于2,则第二个数字标识这样的请求的编号(从1开始),即由具有该编号的请求描述的到达停车场的汽车离开停车场。确保在发出 2 类型请求时该车已停放。汽车的长度是从 1 到 1000 的整数。

输出

对于 1 类型的每个请求,如果相应的汽车无法找到沿街停车的地方,则在单行上打印数字 -1。否则,打印一个数字,该数字等于停放位置的汽车后部与停车场区域起点之间的距离。

示例

输入 #1

30 1 2
6
1 5
1 4
1 5
2 2
1 5
1 4

输出 #1

0
6
11
17
23

输入 #2

30 1 1
6
1 5
1 4
1 5
2 2
1 5
1 4

输出 #2

0
6
11
17
6

输入 #3

10 1 1
1
1 12

输出 #3

-1