AT_abc294_e [ABC294E] 2xN Grid

题目描述

有一个 $2$ 行 $L$ 列的网格。第 $i$ 行 $(i\in\lbrace1,2\rbrace)$，第 $j$ 列 $(1\leq j\leq L)$ 的格子记作 $(i,j)$。在 $(i,j)$ 这个格子上写有整数 $x_{i,j}$。

请你求出满足 $x_{1,j}=x_{2,j}$ 的整数 $j$ 的个数。

不过，$x_{i,j}$ 的信息是通过对 $(x_{1,1},x_{1,2},\ldots,x_{1,L})$ 和 $(x_{2,1},x_{2,2},\ldots,x_{2,L})$ 分别进行游程编码（Run-Length Encoding）后得到的。游程编码后的第 $1$ 行为长度为 $N_1$ 的序列 $((v_{1,1},l_{1,1}),\ldots,(v_{1,N_1},l_{1,N_1}))$，第 $2$ 行为长度为 $N_2$ 的序列 $((v_{2,1},l_{2,1}),\ldots,(v_{2,N_2},l_{2,N_2}))$。

这里，对序列 $A$ 的游程编码是指，将 $A$ 按照相邻不同元素的地方分割，然后对于每一段 $B_i$，$v_i$ 是 $B_i$ 的元素值，$l_i$ 是 $B_i$ 的长度。

输入格式

输入按以下格式从标准输入读入。

$L$ $N_1$ $N_2$ $v_{1,1}$ $l_{1,1}$ $v_{1,2}$ $l_{1,2}$ $\cdots$ $v_{1,N_1}$ $l_{1,N_1}$ $v_{2,1}$ $l_{2,1}$ $v_{2,2}$ $l_{2,2}$ $\cdots$ $v_{2,N_2}$ $l_{2,N_2}$

输出格式

请输出答案，占一行。

输入输出样例 #1

输入 #1

8 4 3
1 2
3 2
2 3
3 1
1 4
2 1
3 3

输出 #1

4

输入输出样例 #2

输入 #2

10000000000 1 1
1 10000000000
1 10000000000

输出 #2

10000000000

输入输出样例 #3

输入 #3

1000 4 7
19 79
33 463
19 178
33 280
19 255
33 92
34 25
19 96
12 11
19 490
33 31

输出 #3

380

说明/提示

限制条件

• $1\leq L\leq 10^{12}$
• $1\leq N_1,N_2\leq 10^5$
• $1\leq v_{i,j}\leq 10^9\ (i\in\lbrace1,2\rbrace,1\leq j\leq N_i)$
• $1\leq l_{i,j}\leq L\ (i\in\lbrace1,2\rbrace,1\leq j\leq N_i)$
• $v_{i,j}\neq v_{i,j+1}\ (i\in\lbrace1,2\rbrace,1\leq j<N_i)$
• $l_{i,1}+l_{i,2}+\cdots+l_{i,N_i}=L\ (i\in\lbrace1,2\rbrace)$
• 输入均为整数

样例解释 1

网格如下图所示。

满足 $x_{1,j}=x_{2,j}$ 的 $j$ 有 $j=1,2,5,8$，共 $4$ 个，所以输出应为 $4$。

样例解释 2

请注意，答案可能超出 $32$ 位整数的范围。

由 ChatGPT 4.1 翻译