## DMOPC '15 Contest 6 P5 - A Classic Problem

View as PDF

Points: 10
Time limit: 1.2s
Memory limit: 256M

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

Given an array with elements, find the number of subarrays such that .

#### Input Specification

The first line will have space-separated and .
The second line will have the array, with each element being between and , inclusive.

#### Output Specification

Output the number of distinct subarrays that satisfy the condition. Two subarrays are different if they occupy a different range of elements, even if the elements themselves are the same.

#### Sample Input

5 2
0 3 2 1 4

#### Sample Output

8

• commented on March 1, 2016, 11:58 p.m.

Can we assume these subarrays are contiguous?

• commented on March 1, 2016, 11:59 p.m.

Yes

• commented on March 1, 2016, 5:49 p.m.

are all the elements unique?

• commented on March 2, 2016, 1:26 p.m.

Can confirm they're not.

• commented on March 1, 2016, 8:46 p.m. edited

Each element being between and , inclusive.

Edit: I misread haha, this quote has nothing to to with your question; sorry Joey ^u^

• commented on March 1, 2016, 6:09 p.m. edited

Two subarrays are different if they occupy a different range of elements, even if the elements themselves are the same.