DMOPC '18 Contest 3 P6 - Bob and Suffering

View as PDF

Submit solution


Points: 30 (partial)
Time limit: 5.0s
Memory limit: 1G

Author:
Problem types

Bob's teachers have conspired to give Bob a major assessment in each of their classes on the same day! Bob has N classes and has estimated how much he will suffer from each assessment. He has recorded these estimates in an array of N positive integers v_1, v_2, \ldots, v_N. He defines the suffering of a subarray to be the product of the minimum element in this subarray and the total sum of the subarray. Given Q queries of the form l r, output the greatest suffering of any subarray contained in the subarray from l to r inclusive where the indices are 1-indexed.

Constraints

1\le v_i \le 1\ 000\ 000
1\le l \le r \le N

Subtask 1 [4%]

N \le 3\ 000, Q \le 10

Subtask 2 [15%]

N\le 5\ 000, Q\le 5\ 000

Subtask 3 [17%]

N\le 100\ 000, Q\le 100\ 000
There are at most 2 different values of v_i

Subtask 4 [24%]

N\le 100\ 000, Q\le 100\ 000
There are at most 20 different values of v_i

Subtask 5 [40%]

N\le 200\ 000, Q\le 200\ 000
No additional constraints

Input Specification

The first line will contain two space-separated integers, N and Q.
The next line will contain N space-separated integers, v_1, \ldots, v_N.
The next Q lines will each contain a query of the form l r.

Output Specification

For each of the Q queries, output a single integer, the largest suffering of a subarray contained in the queried subarray.

Sample Input 1

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

Sample Output 1

25
25
26
30

Explanation for Sample 1

For the first query, the subarray [2, 2] gives a suffering of 5 \cdot 5 = 25.
For the second query, the subarray [2, 2] gives a suffering of 5 \cdot 5 = 25.
For the third query, the subarray [1, 4] gives a suffering of 2\cdot (3+5+2+3)=26.
For the fourth query, the subarray [2, 5] gives a suffering of 2\cdot (5+2+3+5)=30.

Sample Input 2

5 10
1 2 2 3 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Sample Output 2

4
8
14
25
8
14
25
10
25
25

Sample Input 3

10 12
8 2 5 4 1 5 9 8 7 3
1 10
2 4
3 7
7 9
4 6
2 3
7 7
5 10
3 3
1 4
6 8
2 8

Sample Output 3

168
36
81
168
25
25
81
168
25
64
136
136

Comments

There are no comments at the moment.