题目详情题解（0）讨论（0）提交记录（0）

AT_abc294_e.[ABC294E] 2xN Grid

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个 22 行 LL 列的网格。第 ii 行 (i∈{1,2})(i\in\lbrace1,2\rbrace)，第 jj 列 (1≤j≤L)(1\leq j\leq L) 的格子记作 (i,j)(i,j)。在 (i,j)(i,j) 这个格子上写有整数 xi,jx_{i,j}。

请你求出满足 x1,j=x2,jx_{1,j}=x_{2,j} 的整数 jj 的个数。

不过，xi,jx_{i,j} 的信息是通过对 (x1,1,x1,2,…,x1,L)(x_{1,1},x_{1,2},\ldots,x_{1,L}) 和 (x2,1,x2,2,…,x2,L)(x_{2,1},x_{2,2},\ldots,x_{2,L}) 分别进行游程编码（Run-Length Encoding）后得到的。游程编码后的第 11 行为长度为 N1N_1 的序列 ((v1,1,l1,1),…,(v1,N1,l1,N1))((v_{1,1},l_{1,1}),\ldots,(v_{1,N_1},l_{1,N_1}))，第 22 行为长度为 N2N_2 的序列 ((v2,1,l2,1),…,(v2,N2,l2,N2))((v_{2,1},l_{2,1}),\ldots,(v_{2,N_2},l_{2,N_2}))。

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

输入格式

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

LL N1N_1 N2N_2 v1,1v_{1,1} l1,1l_{1,1} v1,2v_{1,2} l1,2l_{1,2} ⋯\cdots v1,N1v_{1,N_1} l1,N1l_{1,N_1} v2,1v_{2,1} l2,1l_{2,1} v2,2v_{2,2} l2,2l_{2,2} ⋯\cdots v2,N2v_{2,N_2} l2,N2l_{2,N_2}

输出格式

请输出答案，占一行。

输入输出样例

  • 输入#1

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

    输出#1

    4

  • 输入#2

    10000000000 1 1
1 10000000000
1 10000000000

    输出#2

    10000000000

  • 输入#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≤L≤10121\leq L\leq 10^{12}
  • 1≤N1,N2≤1051\leq N_1,N_2\leq 10^5
  • 1≤vi,j≤109 (i∈{1,2},1≤j≤Ni)1\leq v_{i,j}\leq 10^9\ (i\in\lbrace1,2\rbrace,1\leq j\leq N_i)
  • 1≤li,j≤L (i∈{1,2},1≤j≤Ni)1\leq l_{i,j}\leq L\ (i\in\lbrace1,2\rbrace,1\leq j\leq N_i)
  • vi,j≠vi,j+1 (i∈{1,2},1≤j<Ni)v_{i,j}\neq v_{i,j+1}\ (i\in\lbrace1,2\rbrace,1\leq j<N_i)
  • li,1+li,2+⋯+li,Ni=L (i∈{1,2})l_{i,1}+l_{i,2}+\cdots+l_{i,N_i}=L\ (i\in\lbrace1,2\rbrace)
  • 输入均为整数

样例解释 1

网格如下图所示。

满足 x1,j=x2,jx_{1,j}=x_{2,j} 的 jj 有 j=1,2,5,8j=1,2,5,8，共 44 个，所以输出应为 44。

样例解释 2

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

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页