2xN Grid

题目描述

我们有一个 $2$ 行 $L$ 列的网格。 令 $(i,j)$ 表示从上数第 $i$ 行 $(i\in\lbrace1,2\rbrace)$、从左数第 $j$ 列 $(1\leq j\leq L)$ 的方格。 $(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})$ 进行游程长度压缩后得到的长度分别为 $N _ 1$ 和 $N _ 2$ 的序列给出：$((v _ {1,1},l _ {1,1}),\ldots,(v _ {1,N _ 1},l _ {1,N _ 1}))$ 和 $((v _ {2,1},l _ {2,1}),\ldots,(v _ {2,N _ 2},l _ {2,N _ 2}))$。 这里，序列 $A$ 的游程长度压缩是由元素 $v _ i$ 和正整数 $l _ i$ 组成的对 $(v _ i,l _ i)$ 的序列，按如下方式得到。

在每一对不同的相邻元素之间将 $A$ 划分开。 对于划分后得到的每个序列 $B _ 1,B _ 2,\ldots,B _ k$，令 $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}$ $\vdots$ $v _ {1,N _ 1}$ $l _ {1,N _ 1}$ $v _ {2,1}$ $l _ {2,1}$ $v _ {2,2}$ $l _ {2,2}$ $\vdots$ $v _ {2,N _ 2}$ $l _ {2,N _ 2}$

输出格式

输出一行，包含答案。

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

4

10000000000 1 1
1 10000000000
1 10000000000

10000000000

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

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\lt N _ i)$ $l _ {i,1}+l _ {i,2}+\cdots+l _ {i,N _ i}=L\ (i\in\lbrace1,2\rbrace)$ 输入中的所有数值均为整数。网格如下所示。 我们有四个满足 $x _ {1,j}=x _ {2,j}$ 的整数 $j$：$j=1,2,5,8$。因此，你应该输出 $4$.
注意答案可能无法装入 32 位整数。

标签: AtCoder|abc294E

来源

AtCoder|abc294E