DMOPC '15 Contest 6 P5 - A Classic Problem

View as PDF

Submit solution

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

Author:
Problem type

Given an array with N elements, find the number of subarrays S such that \max(S) - \min(S) \le K.

Input Specification

The first line will have space-separated N (1 \le N \le 3 \times 10^6) and K (0 \le K \le N).
The second line will have the array, with each element being between 0 and N, 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

Comments


  • 4
    bobbotboy  commented on March 2, 2016, 4:58 a.m.

    Can we assume these subarrays are contiguous?


  • 0
    kobortor  commented on March 1, 2016, 10:49 p.m.

    are all the elements unique?


    • 15
      pyrexshorts  commented on March 2, 2016, 6:26 p.m.

      Can confirm they're not.


    • -2
      bobhob314  commented on March 2, 2016, 1:46 a.m. edited

      Each element being between 0 and N, inclusive.

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


    • 0
      moladan123  commented on March 1, 2016, 11:09 p.m. edit 2

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