DMOPC '15 Contest 6 P5 - A Classic Problem

View as PDF

Submit solution

All submissions

Best submissions

Points: 10

Time limit: 1.2s

Memory limit: 256M

Author:

FatalEagle

Problem type

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

Input Specification

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

Comments

4

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

Can we assume these subarrays are contiguous?

9

FatalEagle commented on March 2, 2016, 4:59 a.m.

Yes

0

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

are all the elements unique?

16

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$ ~0~ and $N$ ~N~, inclusive.

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

1

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.