THICC '17 P5 - Smarties

View as PDF

Submit solution


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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

A certain magical rabbit found a row of N smarties, with the ith 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, \ldots F_{N-1}, 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


  • 3
    Charles232  commented on March 12, 2019, 11:53 a.m.

    THICC


  • -1
    loltrollkill  commented on Nov. 30, 2018, 8:36 p.m.

  • 1
    Ninjaclasher  commented on Oct. 1, 2017, 5: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, 7: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, 1:20 a.m.
      10 4
      1 2 3 4 4 4 1 2 3 4

      correct answer should be 21