#P8178. [POI2020] Les Bitérables

    ID: 8261 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 7 上传者: 标签>CF2300贪心前缀和数学排序动态规划数据结构

[POI2020] Les Bitérables

题目描述

有 tt 个时刻,第 ii 个时刻给出了局面 p1,p2,…,psip_1,p_2,\dots,p_{s_i},表示在数轴的 (0,d)(0,d) 范围内,有且仅有 p1,p2,…,psip_1,p_2,\dots,p_{s_i} 这些位置上有物品。

在 00 位置和 dd 位置有无穷多个物品。

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

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

输入格式

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

接下来 nn 行,每行描述一个时刻的局面,首先是一个非负整数 sis_i,接下来是 sis_i 个正整数,分别为 p1,p2,…,psip_1,p_2,\dots,p_{s_i}。保证 0<p1<p2<⋯<psi<d0<p_1<p_2<\dots<p_{s_i}<d。

输出格式

n−1n-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≤n≤5000002\leq n\leq 500000,2≤d≤10122\leq d\leq 10^{12},∑si≤500000\sum s_i\leq 500000。

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