Deemo's Problem

View as PDF

Submit solution

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

Problem types
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

Deemo has found a problem, and he needs your help! Given an array A of integers (1 \le A_i \le M), find the total number of good subarrays.

A subarray is good if it is non-empty and for every number from 1 to M, they all appear the same number of times.

Input Specification

The first line of input contains N, the length of the array and M.

The second line of input will contain N space separated integers, A_1, A_2 ... A_N.

1 \le M \le N \le 10^5

Output Specification

Output on a single line, the number of good subarrays.

Sample Input 1

3 3
1 2 3

Sample Output 1


Sample Input 2

4 3
1 2 3 1

Sample Output 2



  • 2
    kingW3  commented on April 10, 2020, 11:19 a.m.

    Does subarray (for this particular problem) mean it's contiguous i.e if M=4 and the array is 3 2 4 2 1 is the answer 2 or 0?

    • 0
      sushi  commented on Aug. 23, 2020, 10:27 a.m.

      Correct me if I am wrong, but I have always treated subarrays as being contiguous.