6 人解决,8 人已尝试。
11 份提交通过,共有 20 份提交。
6.5 EMB 奖励。
单点时限: 2.0 sec
内存限制: 512 MB
请注意,本题与(简单)的差别仅在 $m$ 的范围上,其余内容一致。
你和你的队友换了一家评论区未被公关且好评如潮的火锅店吃火锅。
在涮菜的时候,你发现由于下锅时间不一致,而捞出锅时你不一定能捞到你下的菜(也有可能被你急急急的队友给捞走了),你既有可能吃到夹生的鸭肠,也有可能吃到煮久到嚼不动的鸭肠。
我们现在假定,$m$ 种菜品中,菜品 $i$ 需要花 $l_i$ 秒煮熟,而如果 $r_i$ 秒后还没有捞出锅就煮老了;只有在下锅后 $l_i$ 秒到 $r_i$ 秒内捞出的才是恰到好处的。
为了检查你们的涮菜操作是否是合理的,你记录下了完整的操作序列:
你想知道,期望下你能吃到多少份恰到好处的菜。
输入第一行包含两个正整数 $m~(1 \leq m \leq 202\,305), n~(1 \leq n \leq 202\,305)$。
接下来 $m$ 行,每行两个整数 $l_i, r_i (1 \leq l_i \leq r_i \leq 202\,305)$,表示一种菜品的好区间。
接下来 $n$ 行,每行为以下两种中的一种:
其中,$1 \leq t_i \leq 202\,305$,且 $t_i$ 互不相同,并且随着 $i$ 单调增。
输出一行一个整数,表示期望下你能吃到恰到好处的菜的数量对 $998\,244\,353$ 取模的结果。
对答案取模的定义如下:可以证明,答案一定能表示成有理数 $p / q$,其中 $p, q$ 为一对互素的整数(特别地,$p$ 等于 $0$ 时 $q$ 为 $1$)。此时,你需要输出 $p \times q ^ {-1} \bmod 998\,244\,353$,可以证明这个答案唯一。
2 4 1 3 1 7 add 1 add 3 pop 5 pop 7
748683266
2 5 1 4 19 1919 add 1 pop 4 add 114 add 514 pop 1919
1
6 人解决,8 人已尝试。
11 份提交通过,共有 20 份提交。
6.5 EMB 奖励。
创建: 1 年,4 月前.
修改: 1 年,4 月前.
最后提交: 11 月,4 周前.
来源: N/A