THICC '17 P5 - Smarties

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 1.4s
Memory limit: 128M

Author:
Problem type

A certain magical rabbit found a row of N smarties, with the i^\text{th} smartie having flavour F_i. A certain archmage offered the rabbit unlimited carrots if she could figure out how many subarrays had at least 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 and K.
The next line will have N space separated integers, F_1, F_2, \dots, F_N.

Output Specification

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

Constraints

For all subtasks:

1 \le F_i \le 10^6

1 \le K \le N

Subtask 1 [40%]

1 \le N \le 100

Subtask 2 [60%]

1 \le N \le 10^5

Sample Input

5 3
1 2 3 4 5

Sample Output

6

Comments


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

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


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

    THICC


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

  • 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