647 . 柴犬老師的lab收藏

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

33.3% (3/9)

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 編號 ai ， 數字之間以空白分隔。

  • 0<m≤n≤200000
  • 0≤ai≤1000000
subtasks
  • 20% m≤n≤50，ai≤250
  • 40% m≤n≤1000, ai≤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≤50,ai≤250 20
3 8~12 m≤1000,ai≤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