DMOPC '15 Contest 6 P5 - A Classic Problem - Olympiads Online Judge

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) \leq K$ .

Input Specification

The first line will have space-separated $N$ $N$ $(1 \le N \le 3 \times 10^6)$ $(1 \leq N \leq 3 \times 10^{6})$ and $K$ $K$ $(0 \le K \le N)$ $(0 \leq K \leq 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

Copy

5 2
0 3 2 1 4

Sample Output

Copy

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.