AdditionalFile4836.zip

P9403 [POI 2020/2021 R3] Les Bitérables

题目背景

译自 XXVIII Olimpiada Informatyczna - III etap Les Bitérables。

d1t2。

题目描述

有 $t$ 个时刻，第 $i$ 个时刻给出了局面 $p_1,p_2,\dots,p_{s_i}$，表示在数轴的 $(0,d)$ 范围内，有且仅有 $p_1,p_2,\dots,p_{s_i}$ 这些位置上有物品。

在 $0$ 位置和 $d$ 位置有无穷多个物品。

你可以花费一个代价，将一个物品向左移动一个位置或向右移动一个位置。

问你在相邻两个时刻之间，把前一个局面转化为后一个局面，最少需要多少代价。

输入格式

第一行两个正整数 $n,d$。

接下来 $n$ 行，每行描述一个时刻的局面，首先是一个非负整数 $s_i$，接下来是 $s_i$ 个正整数，分别为 $p_1,p_2,\dots,p_{s_i}$。保证 $0<p_1<p_2<\dots<p_{s_i}<d$。

输出格式

$n-1$ 行，每行一个整数，你的答案。

输入输出样例 #1

输入 #1

3 10
2 4 7
3 3 6 8
1 5

输出 #1

4
6

输入输出样例 #2

输入 #2

见附件

输出 #2

6252500
6252500

输入输出样例 #3

输入 #3

见附件

输出 #3

999990000
999990000
999990000
999990000

输入输出样例 #4

输入 #4

生成器：/paste/3igmip11

输出 #4

生成器：/paste/fusadpm0

说明/提示

对于所有数据，$2\leq n\leq 500000$，$2\leq d\leq 10^{12}$，$\sum s_i\leq 500000$。

子任务编号	附加限制	分数
1	$s_i\leq 1$	5
2	$s_i\leq 3$	10
3	$d\leq 7$	12
4	$\sum s_i\leq 5000$	27
5	如果 $s_i>0$，那么 $p_{s_i}=p_1+s_i-1$	11
6		35

#4836. 「POI 2020/2021 R3」Les Bitérables

标签: 传统 | 时间限制: 8000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXVIII Olimpiada Informatyczna – III etap Les Bitérables

字节国家剧院即将上演一出新剧《悲惨比特》（Les Bitérables）。现在是时候为演出准备舞台布景了。导演已经给了你关于每个幕所需布景的指示，你的任务是制定一个计划，让幕间更换布景的时间尽可能短。

对于每一幕，导演都会告诉你舞台上哪些位置需要放置布景元素。所有布景元素看起来都差不多，所以具体哪个元素放在哪个位置并不重要，只要是导演指定的位置即可。我们还假设，在同一幕中，两个布景元素绝不会出现在同一个位置。

并非每一幕都需要用到所有布景元素。未使用的元素需要存放在后台。舞台和后台可以看作一个区间 $[0, d]$，其中位置 $0$ 和 $d$ 是后台，其他整数位置是舞台上的位置。

遗憾的是，更换布景的工作只能由一名技术人员负责。由于布景元素都很重，他一次只能搬运一个。幕间休息时，将一个布景元素从位置 $i$ 搬到位置 $j$ 需要 $|i-j|$ 秒，而其他在舞台上的移动时间可以忽略不计。请你制定一个布景更换计划，让每次幕间休息的时间尽可能短。剧院已经准备了足够的布景元素，如果需要，技术人员可以在后台找到所需的元素。

输入格式

输入的第一行包含两个整数 $n$ 和 $d$ $(2 \leq n \leq 500000, 2 \leq d \leq 10^{12})$，分别表示剧目幕数和字节国家剧院舞台的长度。

接下来的 $n$ 行描述每一幕的布景需求，每行首先包含一个非负整数 $s_{i}$，表示第 $i$ 幕所需的布景元素数量，后面跟着 $s_{i}$ 个递增的整数 $p_{1}, p_{2}, \ldots, p_{s_{i}}$ $(0 < p_{1} < p_{2} < \ldots < p_{s_{i}} < d)$，表示需要放置布景元素的位置。

所有 $s_{i}$ 的总和不超过 $500000$。

输出格式

输出应包含 $n-1$ 行，第 $i$ 行输出一个整数，表示从第 $i$ 幕到第 $i+1$ 幕准备布景所需的最短时间（单位：秒）。

样例 1

输入

3 10
2 4 7
3 3 6 8
1 5

输出

4
6

在第一次幕间休息时，需要移动布景元素：从位置 $4$ 到位置 $3$，从位置 $7$ 到位置 $6$，以及从后台（位置 $10$）到位置 $8$。总共需要 $4$ 秒。

在第二次幕间休息时，需要移动布景元素：从位置 $3$ 到后台（位置 $0$），从位置 $6$ 到位置 $5$，从位置 $8$ 到后台（位置 $10$）。总共需要 $6$ 秒。

样例 2

见附加文件下 [les1.in](file:les1.in) 和 [les1.out](file:les1.out)。

该样例满足 $n=3, d=5001$，第一幕和第三幕不需要布景元素，第二幕需要在位置 $1, 2, \ldots, 5000$ 放置 $5000$ 个布景元素；

样例 3

见附加文件下 [les2.in](file:les2.in) 和 [les2.out](file:les2.out)。

该样例满足 $n=5, d=10^{10}$，第 $j$ 幕需要在位置 $10^{5} \cdot i + 10^{4} \cdot j$（其中 $1 \leq i < 10^{5}, 1 \leq j \leq 5$）放置布景元素；

样例 4

见附加文件下 [les3.in](file:les3.in) 和 [les3.out](file:les3.out)。

该样例满足 $n=500000, d=10^{12}$，第 $i$ 幕在位置 $\left(i^{i} \bmod (d-1)\right)+1$ 放置一个布景元素（其中 $1 \leq i \leq 500000$）。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	对于每个 $i$，$s_{i} \leq 1$	$5$
$2$	对于每个 $i$，$s_{i} \leq 3$	$10$
$3$	$d \leq 7$	$12$
$4$	所有 $s_{i}$ 的总和不超过 $5000$	$27$
$5$	第 $i$ 幕若 $s_{i} > 0$，则 $p_{s_{i}} = p_{1} + s_{i} - 1$	$11$
$6$	无附加限制	$35$