647 . 柴犬老師的lab收藏

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

66.7% (2/3)

Tags

apcsc apcsc-timecomplexity

Description

柴犬老師是一個生活非常無趣的人，他的生活圍繞著柴犬、壽司以及 lab，因此他身邊的人都叫他老師。
柴犬老師實在是強到不行，他加了超級多 lab ，他身邊的人為了衡量他的強度，定義了一個指標：$m$- 強強強指數。
現在我們給柴犬老師的 lab 做編號，並把他最近去過得 $n$ 個 lab 列成一個數列，如果在一個長度 $m$ 的區間內，他去的 $m$ 個 lab 都不一樣，則會有一分的 $m$- 強強強指數。
如果有 $x$ 個這種區間，他的 $m$- 強強強指數就是 $x$。
現在給定 $n$, $m$, 以及柴犬老師最近去過的 lab ，請求出柴犬老師的 $m$- 強強強指數。

Input Format

第一行有兩個數字 $n$ 和 $m$。
第二行有 $n$ 個數字，代表柴犬老師最近去過的 lab 編號 $a_i$ ， 數字之間以空白分隔。

  • $0 < m \leq n \leq 200000$
  • $0 \leq a_i \leq 1000000$
subtasks
  • $20\%$ $m \leq n \leq 50$，$a_i \leq 250$
  • $40\%$ $m \leq n \leq 1000$, $a_i \leq 5000$
  • $100\%$ 無特別限制

Output Format

輸出柴犬老師的 $m$- 強強強指數 $x$。

Sample Input 1

5 3
1 2 3 3 4

Sample Output 1

1

Sample Input 2

6 4
0 1 4 2 1 3

Sample Output 2

2

Sample Input 3

9 4
1 2 3 4 8 7 4 1 1

Sample Output 3

4

Hints

Problem Source

APCS (fixed input range)

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~7 $m \le 50, a_i \le 250$ 20
3 8~12 $m \le 1000, a_i \le 5000$ 20
4 0~22 無額外限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 4
1 1000 524288 65536 1 2 4
2 1000 524288 65536 1 2 4
3 1000 524288 65536 2 4
4 1000 524288 65536 2 4
5 1000 524288 65536 2 4
6 1000 524288 65536 2 4
7 1000 524288 65536 2 4
8 1000 524288 65536 3 4
9 1000 524288 65536 3 4
10 1000 524288 65536 3 4
11 1000 524288 65536 3 4
12 1000 524288 65536 3 4
13 1000 524288 65536 4
14 1000 524288 65536 4
15 1000 524288 65536 4
16 1000 524288 65536 4
17 1000 524288 65536 4
18 1000 524288 65536 4
19 1000 524288 65536 4
20 1000 524288 65536 4
21 1000 524288 65536 4
22 1000 524288 65536 4
Submit
Back to Top