Another Contest 3 Problem 1 - Diverse Arrays

View as PDF

Submit solution


Points: 7
Time limit: 0.6s
Memory limit: 256M

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

Call an array of integers diverse if it has length at least 1 and it has at least K distinct integers.

Given an array of N integers and a parameter K, compute the number of subarrays that are diverse.

Constraints

1 \le K \le N \le 10^6

1 \le a_i \le N

Input Specification

The first line contains two positive integers, N and K.

Each of the next N lines contains a positive integer, a_i. These integers in order comprise the array.

Output Specification

Output the number of subarrays that are diverse.

Sample Input

4 2
1
2
2
2

Sample Output

3

Comments


  • 1
    Inyj  commented on June 1, 2019, 8:52 a.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?


    • 4
      Darcy____Liu  commented on June 1, 2019, 12:01 p.m.

      You are looking for subarrays with at least K = 2 distinct integers

      {1, 2}, {1, 2, 2}, {1, 2, 2, 2} all work because they contain integers 1 and 2


      • 3
        Inyj  commented on June 1, 2019, 3:19 p.m.

        Makes sense, thanks.


  • 5
    IanHu  commented on Dec. 24, 2018, 8:19 p.m. edited

    Hate TLE :-(