E - 2xN Grid Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

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}) をそれぞれ連長圧縮した、長さ N _ 1 の列 ((v _ {1,1},l _ {1,1}),\ldots,(v _ {1,N _ 1},l _ {1,N _ 1})) と長さ N _ 2 の列 ((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 行で出力せよ。

入力例 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 つなので、出力すべき値は 4 です。

入力例 2

10000000000 1 1
1 10000000000
1 10000000000

出力例 2

10000000000

答えが 32\operatorname{bit} 整数に収まらない場合があることに注意してください。

入力例 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

Score : 500 points

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