Another Contest 3 Problem 1 - Diverse Arrays - DMOJ: Modern Online Judge

Another Contest 3 Problem 1 - Diverse Arrays

Submit solution

All submissions

Best submissions

Points: 7

Time limit: 0.3s

Memory limit: 256M

Problem type

Call an array of integers diverse if it has length at least 1 and it has at least $K$ ~K~ distinct integers.

Given an array of $N$ ~N~ integers and a parameter $K$ ~K~, compute the number of subarrays that are diverse.

Constraints

$1 \le K \le N \le 10^6$ ~1 \le K \le N \le 10^6~

$1 \le a_i \le N$ ~1 \le a_i \le N~

Input Specification

The first line contains two positive integers, $N$ ~N~ and $K$ ~K~.

Each of the next $N$ ~N~ lines contains a positive integer, $a_i$ ~a_i~. These integers in order comprise the array.

Output Specification

Output the number of subarrays that are diverse.

Sample Input

Sample Output

Comments

0

kopichiki commented on Aug. 25, 2022, 5:19 p.m. ← edit 5 →

Don't use Python - nobody has passed yet.

PY3: https://dmoj.ca/problem/acc3p1/submissions/?status=AC&language=PY3

PY2: https://dmoj.ca/problem/acc3p1/submissions/?status=AC&language=PY2

Only PyPy 3 works (rarely).

2

Inyj commented on June 1, 2019, 12:52 p.m.

So {1, 2, 2, 2} has subarrays with 2 or more elements:

{1, 2}

{2, 2}

{2, 2}

{1, 2, 2}

{1, 2, 2, 2}

but only {1, 2} is an array of distinct integers.... Am I missing something here? is distinct the wrong adjective or is the sample case wrong?

13

Darcy____Liu commented on June 1, 2019, 4:01 p.m.

You are looking for subarrays with at least $K = 2$ ~K = 2~ distinct integers

{1, 2}, {1, 2, 2}, {1, 2, 2, 2} all work because they contain integers 1 and 2

4

Inyj commented on June 1, 2019, 7:19 p.m.

Makes sense, thanks.

14

IanHu commented on Dec. 25, 2018, 1:19 a.m. ← edited →

Hate TLE :-(

0

mrmackamoo commented on Nov. 24, 2020, 5:53 a.m.

same :)

1

YaySushi commented on Nov. 24, 2020, 5:52 a.m.

Same :-(