THICC '17 P5 - Smarties - DMOJ: Modern Online Judge

THICC '17 P5 - Smarties

Points: 7 (partial)

Time limit: 1.4s

Memory limit: 128M

Author:

Problem type

A certain magical rabbit found a row of $N$ $N$ smarties, with the $i^\text{th}$ $i^{th}$ smartie having flavour $F_i$ $F_{i}$ . A certain archmage offered the rabbit unlimited carrots if she could figure out how many subarrays had at least $K$ $K$ distinct flavours of smarties. Since you too love carrots, you decided to get out your computer and start coding up a solution …

Input Specification

The first line will have 2 space separated integers, $N$ $N$ and $K$ $K$ .
The next line will have $N$ $N$ space separated integers, $F_1, F_2, \dots, F_N$ $F_{1}, F_{2}, \dots, F_{N}$ .

Output Specification

A single integer, the number of subarrays with at least $K$ $K$ distinct flavours of smarties.

Constraints

For all subtasks:

$1 \le F_i \le 10^6$ $1 \leq F_{i} \leq 10^{6}$

$1 \le K \le N$ $1 \leq K \leq N$

Subtask 1 [40%]

$1 \le N \le 100$ $1 \leq N \leq 100$

Subtask 2 [60%]

$1 \le N \le 10^5$ $1 \leq N \leq 10^{5}$

Sample Input

Copy

5 3
1 2 3 4 5

Sample Output

Copy

Comments

-7

bariumlanthanum commented on Dec. 20, 2020, 5:38 p.m.

I prefer smarties to carrots

This comment is hidden due to too much negative feedback. Show it anyway.

10

Charles232 commented on March 12, 2019, 3:53 p.m.

THICC

1

loltrollkill commented on Dec. 1, 2018, 1:36 a.m.

huh.

4

kingW3 commented on Dec. 1, 2018, 11:30 a.m. ← edited →

Your submission is same as this on both problems, clear copy paste.

-1

Plasmatic commented on Dec. 1, 2018, 1:52 a.m. ← edited →

yea we know that already

1

Ninjaclasher commented on Oct. 1, 2017, 9:48 p.m.

It might be worth mentioning that the answer will overflow in an unsigned 32-bit integer (only for Batch #3 though).

0

Ninjaclasher commented on Aug. 6, 2017, 11:14 p.m. ← edited →

Is my solution just upright wrong, or why do I get WA on Batch 5 Case 4?

0
atarw commented on Aug. 7, 2017, 5:20 a.m.
Copy
10 4 1 2 3 4 4 4 1 2 3 4

correct answer should be 21