[R72E]集群 - 代码源竞赛平台

时空限制

1S/512M

题目描述

有 $n$ 台服务器从左到右排列。第 $i$ 台服务器在第 $1,2,\ldots,a_i$ 秒在线，从第 $a_i+1$ 秒开始永久离线；若 $a_i=0$，则该服务器始终离线。

每一秒内，每个无法再向左或向右扩展的连续在线服务器区间组成一个集群。包含 $k$ 台服务器的集群在这一秒会完成 $p_k$ 个任务。

求所有正整数秒内，所有集群完成的任务总数。输出答案对 $998244353$ 取模的结果。

格式

输入格式

第一行包含一个整数 $n$，表示服务器的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 表示第 $i$ 台服务器的在线时长。

第三行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$，其中 $p_k$ 表示一个长度为 $k$ 的集群每秒完成的任务数。

输出格式

输出一个整数，表示所有集群完成的任务总数对 $998244353$ 取模的结果。

样例

样例输入 #1

5
3 1 2 2 3
1 3 6 10 15

样例输出 #1

24

样例解释 #1

第 $1$ 秒有一个长度为 $5$ 的集群，完成 $15$ 个任务；第 $2$ 秒的两个集群长度分别为 $1,3$，共完成 $1+6=7$ 个任务；第 $3$ 秒有两个长度为 $1$ 的集群，共完成 $2$ 个任务。因此答案为 $15+7+2=24$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	$a_i\le$
$1$	$30$	$2000$
$2$	$30$	$10^5$
$3$	$40$	$2\times10^5$	$10^9$

对于 $100\%$ 的数据，满足 $1\le n\le2\times10^5$，$0\le a_i\le10^9$，$0\le p_i\le10^9$。