DMOPC '17 Contest 1 P5 - Intimidating Arrays

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

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

Call an element of an array A a peak of A if it is larger than all elements before it in A. The intimidation value of an array is the number of peaks of A.

For example, the intimidation value of 1, 2, 3, 4, 5 is 5 and the intimidation value of 5, 4, 3, 2, 1 is 1 (only 5 is intimidating).

You are given a permutation of 1, 2, \ldots, N and are asked to answer Q queries. These queries are of the form l r and you must output the intimidation value of the subarray from l to r inclusive. Note that an element can be a peak of a subarray, but not a peak of the entire array. However, the intimidation value of the subarray would account for this element, while it would not be counted for the entire array.


For all subtasks, 1\leq l\leq r \leq N.

Subtask 1 [30%]

N\leq 2000
Q\leq 5000

Subtask 2 [70%]

N\leq 10^6
Q\leq 10^6

Input Specification

The first line of the input will have two integers, N and Q.

The second line of the input will have N integers: the given permutation of 1, 2, \ldots, N.

The following Q lines contain two space-separated integers each. These values are l and r of each query.

Output Specification

For each query, output the answer on a new line.

Sample Input 1

4 3
2 1 4 3
1 4
2 3
3 4

Sample Output 1


Sample Input 2

6 4
6 5 1 2 3 4
2 6
3 5
1 6
4 4

Sample Output 2



There are no comments at the moment.