#P18952. [Mladen Manev 2022 AT2] play / 舞台道具搬运

[Mladen Manev 2022 AT2] play / 舞台道具搬运

舞台道具搬运

一条长为 DD 的直线舞台的两端分别是位置 0,D0,D,两端仓库都可无限供应和存放同一种道具。共有 NN 幕演出,第 ii 幕要求在给定的 SiS_i 个位置各放一件道具,其余舞台内部位置没有道具。

相邻两幕之间,可以移动道具,也可以从任一端仓库取出或送入道具。一次搬运一件道具,从位置 xx 移到 yy 的代价为 ∣x−y∣|x-y|。空手走动不计代价。道具互相不可区分。

分别求从第 ii 幕布置变为第 i+1i+1 幕布置的最小总搬运代价,1≤i<N1\le i<N。

输入格式

第一行 N,DN,D。接下来 NN 行,每行先给出 SiS_i,再给出严格递增的 SiS_i 个整数位置。

输出格式

输出 N−1N-1 行,第 ii 行是相邻两幕之间的最小代价。使用 64 位整数。

数据范围

2≤N≤5000002\le N\le500000,2≤D≤10122\le D\le10^{12},Si≥0S_i\ge0,∑Si≤500000\sum S_i\le500000。每个位置 PP 满足 0<P<D0<P<D。Si=0S_i=0 时该行只有一个零。

样例

3 10
2 4 7
3 3 6 8
1 5
4
6

本题为波兰 XXVIII OI 决赛第一天 Les Bitérables(2021),由本网站 2022 年训练赛选用。

来源与数据说明

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

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