题目要求模拟包裹提取过程,需要高效支持以下操作:
因此,可以使用线段树来维护每个存储格的有效最迟提取日。
在一个物流中心,有一排共 m 个存储格,编号为 1 到 m。每个存储格内放置了一个包裹,第 i 个包裹有一个最迟提取日 ei,表示该包裹可以在第 ei 天或之前被提取。
现在有 n 名员工依次来处理订单。第 i 名员工在第 dayi 天来到仓库,并需要从编号在 [li,ri] 区间内的存储格中提取一个包裹。提取规则如下:在该区间内,所有尚未被提取的包裹中,选择最迟提取日最大的包裹;如果最大值对应多个包裹,则选择编号最小(即最靠左)的那一个。如果区间内所有包裹的最迟提取日均小于 dayi(即全部已失效),则该员工无法提取任何包裹。
当一名员工提取了一个包裹后,该存储格随即被清空,后续员工无法再从中提取。
请你计算出每一名员工最终提取的包裹所在存储格的编号;如果某员工未能提取,对应输出 −1。
数据范围
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.