TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3480
  • 题目
  • P3480【2015多校联训2】阿 Q 的停车场
    限制 : 时间限制 : 20000 MS   空间限制 : 265536 KB
    问题描述

    刚拿到驾照的 KJ 总喜欢开着车到处兜风,玩完了再把车停到阿 Q 的停车场里,虽然 她对自己停车的水平很有信心,但她还是不放心其他人的停车水平,尤其是 Kelukin。于是, 她每次都把自己的爱车停在距离其它车最远的一个车位。KJ 觉得自己这样的策略非常科 学,于是她开始想:在一个停车场中有一排车位,从左到右编号为 1 到 n,初始时全部是 空的。有若干汽车,进出停车场共 m 次。对于每辆进入停车场的汽车,会选择与其它车距 离最小值最大的一个车位,若有多个符合条件,选择最左边一个。KJ 想着想着就睡着了, 在她一旁的 Kelukin 想帮她完成这个心愿,但是他又非常的懒,不愿意自己动手,于是就把 这个问题就留给了你:在 KJ 理想的阿 Q 的停车场中,给你车辆进出的操作序列,依次输 出每辆车的车位编号。

    输入格式

    第一行,两个整数 n 和 m,表示停车场大小和操作数;
    接下来 m 行,每行两个整数 F 和 x F 是 1 表示编号为 x 的车进停车场; F 是 2 表示编号为 x 的车出停车场;
    保证操作合法,即: 出停车场的车一定目前仍在停车场里; 停车场内的车不会超过 n;

    输出格式

    对于所有操作 1,输出一个整数,表示该车车位的编号

    样例输入

    7 11 
    1 15 
    1 123123 
    1 3 
    1 5 
    2 123123 
    2 15 
    1 21 
    2 3 
    1 6 
    1 7 
    1 8

    样例输出

    1






    3

    提示

    【数据范围】
    对 30%的数据 n<=1000 ,m<=1000 对
    60%的数据 n<=200000,m<=2000
    对 100%的数据 n,m<=200000,
    车的编号小于等于 10^6


    来源  by BS