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

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 3.0s
Java 5.0s
Memory limit: 256M
Java 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, A_3, \ldots A_N, and has defined the k-\textbf{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-\text{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-\text{interest} of the subarray A_l, A_{l+1}, \ldots A_{r-1}, A_r.

Can you write a program to help Dr. Henri?

Constraints

Subtask 1 [10%]

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

Subtask 2 [60%]

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

Subtask 3 [30%]

1 \leq N, Q \leq 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, A_3, \ldots, 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 \leq l_i \leq r_i \leq N and 1 \leq k_i \leq 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


  • 1
    BlueCat  commented on Dec. 18, 2018, 8:45 a.m.

    Good Problem!


  • 5
    1419903188  commented on Dec. 13, 2018, 7:52 a.m.

    A similar problem which is a 20-pointer


    • -10
      ss__jonathan  commented on Dec. 14, 2018, 11:34 a.m. edit 2

      This comment is hidden due to too much negative feedback. Click here to view it.


      • 10
        whomax  commented on Dec. 14, 2018, 3:24 p.m.

        Leave it to ss__jonathan to lower the point values of the questions he deems to be “easy” #geeksforgeeks


        • -6
          ss__jonathan  commented on Dec. 14, 2018, 5:16 p.m.

          This comment is hidden due to too much negative feedback. Click here to view it.


    • -4
      imathblue  commented on Dec. 13, 2018, 10:32 p.m.

      Selective Cutting is pretty overrated tbh