atcoder#ABC294E. [ABC294E] 2xN Grid
[ABC294E] 2xN Grid
题目描述
行 列のマス目があります。 上から 行目 、左から 列目 のマス目を で表します。 には整数 が書かれています。
であるような整数 の個数を求めてください。
ただし、 の情報は と をそれぞれ連長圧縮した、長さ の列 $ ((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})) $ として与えられます。
ここで、列 の連長圧縮とは、 の要素 と正整数 の組 の列であって、次の操作で得られるものです。
- を異なる要素が隣り合っている部分で分割する。
- 分割した各列 に対して、 を の要素、 を の長さとする。
输入格式
入力は以下の形式で標準入力から与えられる。
输出格式
答えを 行で出力せよ。
题目大意
现在有两个长度为 的序列 ,找出有多少个下标 满足 。
由于 十分地大,因此 被体现为一个长度为 的二元组序列。下面是二元组序列的生成方式:
- 对于所有 序列中的 ,我们在 中间切割一次。
- 最后 序列会被切割成 块,每一块都是由 个相同的数 组成的。我们将每一块表示成一个二元组 ,从左至右拼接起来即可得到一个长度为 的二元组序列。
同理, 被体现为一个长度为 的二元组序列。
给出 以及两个二元组序列,解决本题开头的问题。
Translated by
https://www.luogu.com.cn/user/399150
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\ 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) $
- 入力はすべて整数
Sample Explanation 1
マス目は以下の図のようになっています。 ![](https://img.atcoder.jp/abc294/14f38720983c464a322b504738344f24.png) となるような整数 は、 の つなので、出力すべき値は です。
Sample Explanation 2
答えが 整数に収まらない場合があることに注意してください。