#P18954. [Mladen Manev 2022 AT4] snowcleaning / 动态充电站与清雪

[Mladen Manev 2022 AT4] snowcleaning / 动态充电站与清雪

动态充电站与清雪

一条道路是线段 [0,L][0,L]。清雪车每次充满电后可以清理总长为 KK 的积雪。沿道路有 NN 个充电站,位置严格递增;充电瞬间完成,可以随时充满。

清雪车可以带电或不带电行驶,行驶一单位距离需要一单位时间。只有清理积雪才消耗电量;经过某段道路时可以选择清理,也可以不清理。可以重复经过已经清理的路段;转向没有额外开销。

连续处理 DD 天。每天开始时整条道路重新被积雪覆盖,电池为空,车位于当日给出的 PP。当夜有一些坏站修复、一些正常站损坏;站点状态持续到后续日期,且每天至少有一个站正常。初始全部站正常。

求每天清理整条道路所需的最短时间。车最后可以停在任意位置,不必返回充电站。

输入格式

第一行 N,L,K,DN,L,K,D。第二行严格递增的 NN 个站点位置 XiX_i。

接下来每一天有三行:第一行 Z,U,PZ,U,P,表示修复站数、损坏站数及车的起始位置;第二行为递增的 ZZ 个修复站编号,第三行为递增的 UU 个损坏站编号。编号从 11 开始,空列表对应空行。

修复的站此前一定损坏,损坏的站此前一定正常;当日两类编号互不相交。

输出格式

DD 行,每行一个 64 位整数,表示该天的最短清雪时间。

数据范围

1≤N,D≤2500001\le N,D\le250000,1≤K≤L≤1091\le K\le L\le10^9,0≤X1<⋯<XN≤L0\le X_1<\cdots<X_N\le L,0≤P≤L0\le P\le L。全部日期修复数之和不超过 500000500000,损坏数之和也不超过 500000500000,二者分别限制。

样例

3 5 2 1
2 3 5
0 1 3

2
9

从位置 3 先到正常站 2 充电,清理左侧后返回;再充电清理右侧,并利用站 5,最终可以停在位置 4,总行驶距离为 9。

本题为波兰 XXVIII OI 决赛第一天 Surowa zima(2021),由本网站 2022 年训练赛选用。官方解法见 OI 分析。

来源与数据说明

2022 年 Dr. Mladen Manev,AT4,原题名 snowcleaning。赛事资料,原文题面见附件 statement.pdf。

原官方测试数据未能获取,本题使用依据原题规格编写的自建测试数据,并非官方原始数据。总分为 100 分。