比赛场次 | 687 |
---|---|
比赛名称 | 树状数组练习 |
比赛状态 | 正在进行... |
开始时间 | 2025-06-11 18:00:00 |
结束时间 | 2025-06-15 22:00:00 |
开放分组 | 全部用户 |
注释介绍 | 不定时测评 |
题目名称 | 排队买票 |
---|---|
输入输出 | buytickets.in/out |
时间限制 | 1000 ms (1 s) |
内存限制 | 256 MiB |
测试点数 | 10 简单对比 |
在铁路实行互联网购票之前,每年春运时,火车站里人们总是排着长队购买回家的车票。
又到了一年一度的春运,ACM大牛因为在学校集训回家很晚,虽然很不情愿,大牛还是在半夜(为了不影响自己白天集训)冒着寒风到火车站购票。
来到火车站后,大牛发现人很多而且很乱,具体表现为很多人插队(强烈谴责)。那么,如果为队列中的每个人分配一个整数值作为他的编号并且告诉你他插队的位置,你能确定每个人最终的顺序吗?
输入数据可能存在多组。
对于每组输入数据,第一行包含一个整数$n$,表示排队的总人数。
接下来$n$行,每行两个整数$p_i$,$v_i$,分别表示第$i$个人插队时前面人的个数以及他的个人编号。
例如,$p_i=0$,表示这个人插到了队首,$p_i=2$表示插队插到了第$3$个位置(前面有$2$个人)。
每组输入数据,输出一行包含$n$个整数(表示每个人的编号)的结果,表示最终的人员队列顺序。
每组结果占一行,同行数据之间空格隔开。
4 0 77 1 51 1 33 2 69 4 0 20523 1 19243 1 3890 0 31492
77 33 69 51 31492 20523 3890 19243
对于第一组输入数据。
77号入队,插在队首,队列为77;
51号入队,前面有一个人,队列为77 51;
33号入队,前面有一个人,队列为77 33 51;
69号入队,前面有两个人,队列为77 33 69 51。
$1\leq n\leq 2\times 10^5,0\leq p_i\leq i-1,0\leq v_i\leq 32767$。