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 \leq K \leq N \leq 10^{6}$

$1 \le a_i \le N$ $1 \leq a_{i} \leq 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

Copy

Sample Output

Copy

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).

3

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?

14

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 :-(