102944: [Atcoder]ABC294 E - 2xN Grid

Problem Statement

We have a grid with $2$ rows and $L$ columns. Let $(i,j)$ denote the square at the $i$-th row from the top $(i\in\lbrace1,2\rbrace)$ and $j$-th column from the left $(1\leq j\leq L)$. $(i,j)$ has an integer $x _ {i,j}$ written on it.

Find the number of integers $j$ such that $x _ {1,j}=x _ {2,j}$.

Here, the description of $x _ {i,j}$ is given to you as the run-length compressions of $(x _ {1,1},x _ {1,2},\ldots,x _ {1,L})$ and $(x _ {2,1},x _ {2,2},\ldots,x _ {2,L})$ into sequences of lengths $N _ 1$ and $N _ 2$, respectively: $((v _ {1,1},l _ {1,1}),\ldots,(v _ {1,N _ 1},l _ {1,N _ 1}))$ and $((v _ {2,1},l _ {2,1}),\ldots,(v _ {2,N _ 2},l _ {2,N _ 2}))$.

Here, the run-length compression of a sequence $A$ is a sequence of pairs $(v _ i,l _ i)$ of an element $v _ i$ of $A$ and a positive integer $l _ i$ obtained as follows.

1. Split $A$ between each pair of different adjacent elements.
2. For each sequence $B _ 1,B _ 2,\ldots,B _ k$ after the split, let $v _ i$ be the element of $B _ i$ and $l _ i$ be the length of $B _ i$.

Constraints

• $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)$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$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}$

Output

Print a single line containing the answer.

Sample Input 1

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

Sample Output 1

4

The grid is shown below.

We have four integers $j$ such that $x _ {1,j}=x _ {2,j}$: $j=1,2,5,8$. Thus, you should print $4$.

Sample Input 2

10000000000 1 1
1 10000000000
1 10000000000

Sample Output 2

10000000000

Note that the answer may not fit into a $32$-bit integer.

Sample Input 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

Sample Output 3

380

问题描述

我们有一个有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$的运行长度压缩是一个由$A$中的元素$v _ i$和正整数$l _ i$组成的序列$(v _ i,l _ i)$，如下所示。

1. 在每对相邻的不同元素之间分割$A$。
2. 对于分割后的每个序列$B _ 1,B _ 2,\ldots,B _ k$，令$v _ i$为$B _ i$中的元素，$l _ i$为$B _ i$的长度。

约束

• $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)$
• 输入中的所有值都是整数。

输入

输入是通过标准输入按以下格式给出的：

$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}$

输出

打印一行答案。

样例输入1

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

样例输出1

4

网格如下所示。

我们有四个满足$x _ {1,j}=x _ {2,j}$的整数$j$：$j=1,2,5,8$。因此，你应该打印$4$。

样例输入2

10000000000 1 1
1 10000000000
1 10000000000

样例输出2

10000000000

请注意，答案可能不适用32位整数。

样例输入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