No.3324 ハイライト動画
タグ : / 解いたユーザー数 59
作問者 : 👑
loop0919
/ テスター :
高橋ゆに
あじゃじゃ
DeltaStruct
elphe
bolero
問題文
岩井星人さんのショート動画や動画の開幕には、実況動画の一部を切り取ったハイライト動画があります。
とても面白いので、ここだけでも見ましょう。
$N$ 個のフレームからなる 実況動画 と、$M$ 個のフレームからなる ハイライト動画 があります。
ハイライト動画のフレーム $i$ $(1 \leq i \leq M)$ は、実況動画のフレーム $A_i$ となっています。
ここで、$A = (A_1, A_2, \cdots, A_M)$ は数列 $(1, 2, \cdots, N)$ の（連続とは限らない）部分列であることが制約により保証されます。
あなたの仕事は、ハイライト動画が実況動画のどのシーンから切り取られたかを特定することです。
最小のシーン数 $X$ と、各 $k ~ (1 \leq k \leq X)$ について $k$ 番目のシーンの開始フレーム $S_k$ とその長さ $L_k$ を求めてください。
より厳密には、以下の条件を満たす整数 $X$ の最小値と、そのときの長さ $X$ の列 $\big((S_1, L_1), (S_2, L_2), \cdots, (S_X, L_X)\big)$ を求めてください。
ここで、正整数 $s, l$ について $[s, s + l)$ を数列 $(s, s + 1, \cdots, s + l - 1)$ と定義します。
- $A$ を連続部分列に分割したとき、$X$ 個の数列 $[S_1, S_1 + L_1), [S_2, S_2 + L_2), \cdots, [S_X, S_X + L_X)$ にすることが可能である。
連続部分列に分割するとは
数列 $A$ を連続部分列に分割するとは、以下の手続きのことです。
- 分割後の数列の個数 $x ~ (1 \leq k \leq N)$ および $1 = i_1 \lt i_2 \lt \cdots \lt i_x < i_{x + 1} = N + 1$ を満たす整数列 $(i_1, i_2, \cdots, i_x, i_{x + 1})$ を自由に選ぶ。
- $1 \leq n \leq x$ について、$n$ 番目の数列を、$A$ の $i_n$ 番目から $i_{n + 1} - 1$ 番目までの要素を順番を保ったまま取り出してできる数列とする。
$A = (1, 2, 3, 4, 5)$ を連続部分列に分割するときの例は以下の通りです。
- $(1, 2, 3), (4), (5)$
- $(1, 2), (3, 4, 5)$
- $(1, 2, 3, 4, 5)$
制約
- $1 \le N \le 10^9$
- $1 \le M \le \min(N, 2 \times 10^5)$
- $1 \le A_1 < A_2 < \cdots < A_M \le N$
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $M$ $A_1$ $A_2$ $\dots$ $A_M$
出力
最小のシーン数 $X$ と、各 $k$ について、$k$ 番目のシーンの開始フレーム $S_k$ とその長さ $L_k$ を以下の形式で出力せよ。
$X$ $S_1$ $L_1$ $S_2$ $L_2$ $\vdots$ $S_X$ $L_X$
サンプル
サンプル1
入力
10 6 1 2 4 5 6 10
出力
3 1 2 4 3 10 1
$(1, 2), (4, 5, 6), (10)$ のように分割すると、$3$ 個のシーンに分割することができます。$2$ 個以下のシーンに分割することはできないため、これが最小です。
サンプル2
入力
5 5 1 2 3 4 5
出力
1 1 5
サンプル3
入力
360000 14 1 2 3 12 13 14 15 16 359995 359996 359997 359998 359999 360000
出力
3 1 3 12 5 359995 6
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。