← 返回题目列表

Codeforces · 780/G

G. Andryusha 和神经障碍

中文机器翻译题面 查看原题

Andryusha 发现了一台令人费解的街机。该机器是一块垂直调整的板,分为方形单元。棋盘有 w 列,从左到右编号为 1 到 w,h 行从下到上编号为 1 到 h。

此外,一些板行中存在障碍物。总共有 n 个障碍,其中第 i 个障碍占据​​了 ui 行的 li 到 ri 单元格。 Andryusha 记得很清楚,没有两个障碍物共用同一排。此外,没有一行完全被屏障占据,即每行中至少有一个单元是空闲的。

玩家可以从上方向机器的任意柱投掷弹珠。弹珠向下落,直到遇到障碍物,或落入棋盘底部。一旦遇到障碍物,弹珠就会消失,但会被同一障碍物左侧和右侧的另外两个弹珠取代。在障碍物位于棋盘边缘的情况下,两个弹珠都会出现在与边缘相对的一侧的障碍物旁边。多个弹珠可以占据棋盘的同一位置,而不会妨碍彼此的移动。最终,所有弹珠都必然从机器底部掉落。

大理石与屏障相互作用的示例。

奇怪的是,有时弹珠可以像自由细胞一样穿过障碍物。之所以如此,是因为这些屏障实际上是​​活的,当弹珠从很高的高度向它们袭来时,它们就会受到惊吓。更具体地说,如果弹珠从高于 si 的相对高度落向障碍物 i(即,它开始下落的高度严格高于 ui + si),则障碍物会避开弹珠。如果从棋盘顶部抛出一个弹珠,则认为它出现在高度 (h + 1) 处。

Andryusha 记得在每根柱子里扔过一次弹珠。帮助他找出落在机器底部的弹珠总数。由于答案可能很大,因此将其打印为 109 + 7 模。

输入

第一行包含三个整数 h、w 和 n (1 ≤ h ≤ 109, 2 ≤ w ≤ 105, 0 ≤ n ≤ 105)——分别是机器中的行数、列数和栅栏数。

接下来的 n 行描述了障碍。其中第 i 行包含四个整数 ui、li、ri 和 si(1 ≤ ui ≤ h、1 ≤ li ≤ ri ≤ w、1 ≤ si ≤ 109)——行索引、第 i 个障碍物的最左和最右列索引,以及障碍物无法躲避下落弹珠的最大相对下落高度。保证每一行至少有一个空闲单元,并且所有 ui 都是不同的。

输出

打印一个整数——以 109 + 7 为模的问题的答案。

示例

输入 #1

10 5 1
3 2 3 10

输出 #1

7

输入 #2

10 5 2
3 1 3 10
5 3 5 10

输出 #2

16

输入 #3

10 5 2
3 1 3 7
5 3 5 10

输出 #3

14

输入#4

10 15 4
7 3 9 5
6 4 10 1
1 1 4 10
4 11 11 20

输出#4

53

注意

在第一个示例案例中,有一个障碍:如果有人在第二列或第三列中扔一个弹珠,则会出现两个弹珠,否则只有一个弹珠。总答案是7。

在第二个示例案例中,生成的弹珠数量为 2、2、4、4、4(按照初始弹珠索引列的顺序)。

在第三个示例案例中,生成的弹珠数量为 1, 1, 4, 4, 4。请注意,第一个障碍物会躲避从棋盘顶部落下的弹珠,但不会躲避从第二个障碍物落下的弹珠。

在第四个示例中,生成的弹珠数量为 2, 2, 6, 6, 6, 6, 6, 6, 6, 1, 2, 1, 1, 1, 1。下图显示了弹珠被扔进第七列的情况。

将弹珠扔进第七根柱子的结果。