ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#8503
サブタスク

적어도 하나씩 만들기 5s 1024MB

問題

길이 N의 수열이 주어진다.

정수 K에 대해, 다음의 조건을 만족하는 구간을 'K-좋은 구간'이라 정의하자.

  • 1\leq x\leq K를 만족하는 모든 x에 대해, 구간 내에 정확히 x개 존재하는 숫자가 적어도 하나 존재한다.

어떤 수열과 정수 K가 주어졌을 때, K-좋은 구간의 개수를 구해보자.


入力

첫 줄에 N과 K가 공백으로 구분되어 주어진다. (1\leq N\leq 10^5 , 1\leq K\leq 4)

그 다음 줄에 길이 N의 수열이 주어진다. 각 원소는 1 이상 N 이하의 자연수이다.


出力

주어진 수열에 대해 K-좋은 구간의 개수를 한 줄에 출력하여라.


部分問題

番号 点数 条件
#120点

N\leq 1000

#215点

수열의 모든 원소는 1 이상 K 이하의 자연수이다.

#335点

K=1

#430点

추가 제한 조건 없음


例題 #1

3 1
1 2 1
6

모든 구간이 1-좋은 구간이다.


例題 #2

6 3
6 5 6 4 5 5
1

전체 구간이 유일한 3-좋은 구간이다.


例題 #3

6 2
5 4 5 2 6 5
5


出典

COCI 2024/2025 Contest #1

ログインしないとコードを書けません。