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

View as PDF

Submit solution


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

Author:
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

Dr. Henri is working on a new method of analyzing lab data! He has collected N data points: A_1, A_2, A_3, \dots, 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}, \dots, A_{r-1}, 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, A_3, \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 \leq 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


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

    Good Problem!


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

    A similar problem which is a 20-pointer


    • 3
      Rimuru  commented on Dec. 14, 2018, 11:34 a.m. edit 3

      Selective cutting has been turned down to 15 points and rescored.


      • 11
        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


        • 3
          Rimuru  commented on Dec. 14, 2018, 5:16 p.m. edited

          I think it would be best to note that I wasn't the one to lower the point value for selective cutting.


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

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