#P13076. [NOISG 2019] Lasers

    ID: 12876 Type: RemoteJudge 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>2019NOISG(新加坡)

[NOISG 2019] Lasers

题目背景

熊猫先生知道小猫非常喜欢激光玩具,于是他决定给 Rar the Cat 买一个激光玩具。

题目描述

这个激光玩具的顶部有 LL 个间距均匀的激光,全部朝下。第 11 个激光距离左边缘 0.50.5 个单位,第 LL 个激光距离右边缘 0.50.5 个单位,相邻激光之间距离为 11 个单位。

该玩具共有 RR 排滑动的挡板,每排有若干不重叠的挡板。具体来说:

  • 每排有若干长度为正整数的挡板,总长度不超过 LL
  • 同一排内,所有挡板可以整体平移,但挡板之间相对位置不变,且不会重叠。
  • 一个宽度为 xx 的挡板可以完全阻挡连续 xx 个激光。

请你计算,在所有挡板可能的配置中,有多少个激光会始终被至少一个挡板阻挡。

输入格式

第一行包含两个整数 LLRR

接下来 RR 行描述每排的挡板情况,每行格式如下:

  • 一个整数 XX,表示该排有 XX 个挡板。
  • 接下来 XX 个整数,依次表示每个挡板的宽度,第一个整数是最左边挡板的宽度。

保证每排所有挡板的总宽度不超过 LL

输出格式

输出一个整数,表示始终被至少一个挡板阻挡的激光数量。

11 3
2 2 3
1 7
2 4 1
3
10 3
3 1 5 1
4 2 2 3 1
3 1 6 2
6
10 1
1 4
0

提示

【样例解释】

对于样例 1:

22 排有一个宽度为 77 的挡板,它无论怎么移动,第 556677 号激光总会被阻挡。

对于样例 2:

334455667799 号激光始终被至少一个挡板阻挡。

对于样例 3:

所有激光在至少一种挡板配置下都可以通过。

【数据范围】

  • 1R5×1051 \leq R \leq 5 \times 10^5
  • 1L1091 \leq L \leq 10^9
  • 1X5×1051 \leq \sum X \leq 5 \times 10^5
  • 每排所有挡板宽度和不超过 LL
子任务编号 分值 额外限制
11 1010 R=1, X=1R = 1,\ X = 1
22 1414 X=1X = 1
33 2020 R=2, 1L106R = 2,\ 1 \leq L \leq 10^6
44 2121 1L103, 1X1031 \leq L \leq 10^3,\ 1 \leq \sum X \leq 10^3
55 2222 1L1061 \leq L \leq 10^6
66 1313 无额外限制