DMOPC '18 Contest 4 P4 - Dr. Henri and Lab Data

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 1.4s
Java 2.5s
Memory limit: 256M

Author:
Problem type

Dr. Henri is working on a new method of analyzing lab data! He has collected N data points: A_1, A_2, \dots, A_N, and has defined the k-interest of a subarray as the sum of all numbers greater than or equal to k minus the sum of all numbers less than k.

For example, the 5-interest of the array [4, 2, 6, 5, 1] is (6+5)-(4+2+1) = 4.

Dr. Henri knows that some of the data might be outliers, so he asks you Q queries of the form l r k, asking you to compute the k-interest of the subarray A_l, A_{l+1}, \dots, A_r.

Can you write a program to help Dr. Henri?

Constraints

Subtask 1 [10%]

1 \le N, Q \le 4\,000
1 \le A_i \le 10^9

Subtask 2 [60%]

1 \le N, Q \le 200\,000
1 \le A_i \le 200\,000

Subtask 3 [30%]

1 \le N, Q \le 200\,000
1 \le A_i \le 10^9

Input Specification

The first line of input will contain two space-separated integers, N and Q.
The second line of input will contain N space-separated integers, A_1, A_2, \dots, A_N.
The next Q lines will each contain three space-separated integers, l_i, r_i, and k_i.
It is guaranteed that 1 \le l_i \le r_i \le N and 1 \le k_i \le 10^9.

Output Specification

Q lines, where the i^\text{th} line is the answer to the i^\text{th} query.

Sample Input 1

3 6
5 10 15
1 2 1
1 3 16
2 2 10
2 2 11
1 3 6
1 1 9

Sample Output 1

15
-30
10
-10
20
-5

Sample Input 2

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

Sample Output 2

17
49
-9
13
-15
4
-30
5
21
18

Comments