网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[HAOI2013]软件安装
成绩 | 开启时间 | 2014年09月19日 星期五 10:07 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:07 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:07 |
输入文件 | haoi13t4.in | 输出文件 | haoi13t4.out |
Dr.Kong有一个容量为N MB (1 <= N <= 50,000)的存储磁盘,不妨设地址空间编号为1到N。现在他需要安装一些软件, 每个软件要占用一定大小的容量且必须装在连续的地址空间里。比如发出指令“1 100”,表示需要申请100 MB的存储空间。如果有多个满足条件的连续空间,则选择起始地址最小的一个进行分配。若没有足够的连续空间,将不安装此软件(即使有足够多的不连续存储空间)。
系统可以不定时的卸载软件,释放磁盘的空间。比如:发出“2 23 100”,表示释放起始地址为23的连续100MB大小的容量。释放时,不需要考虑这些空间里是否安装过软件。
请你编写一个程序,帮助Dr.Kong处理M (1 <= M <= 50,000)个按指令次序请求的任务。第一个请求到来前,磁盘是空的。
输入格式:
第1行: N M
第2..M+1行: 每行描述了一个请求,如果是申请,则用2个数字 1 Mi 表示; 如果是释放,则用3个数字 2 Di Mi表示。数据之间用一个空格隔开
(1<=Di ,Mi<= 50,000)
输出格式:
对于每个申请指令,输出1行。如果请求能被满足,输出满足条件的最小起始地址;如果请求无法被满足,输出0。
输入样例 :
10 6
1 3
1 3
1 3
1 3
2 5 5
1 6
输出样例 :
1
4
7
0
5