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^\text{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 \le F_i \le 10^6~

$1 \le K \le N$ ~1 \le K \le N~

Subtask 1 [40%]

$1 \le N \le 100$ ~1 \le N \le 100~

Subtask 2 [60%]

$1 \le N \le 10^5$ ~1 \le N \le 10^5~

Sample Input

5 3
1 2 3 4 5

Sample Output

Comments

-6

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.

0

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.
10 4 1 2 3 4 4 4 1 2 3 4

correct answer should be 21