← 返回题目列表

AtCoder · abc294_e

H. 2xN 网格

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

我们有一个网格 2 行和 L 列。 让 (i,j) 表示 i从顶部算起的第行 (i\in\lbrace1,2\rbrace) 和 j左起第 列 (1\leq j\leq L). (i,j) 有一个整数 x _ {i,j} 。

查找整数的个数 j 这样 x _ {1,j}=x _ {2,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 of A 和一个正整数 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

网格如下所示。

我们有四个整数 j 这样 x _ {1,j}=x _ {2,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