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

View as PDF

Points: 15 (partial)
Time limit: 3.0s
Java 5.0s
Memory limit: 256M

Author:
Problem type

Dr. Henri is working on a new method of analyzing lab data! He has collected data points: , and has defined the of a subarray as the sum of all numbers greater than or equal to minus the sum of all numbers less than .

For example, the of the array is .

Dr. Henri knows that some of the data might be outliers, so he asks you queries of the form l r k, asking you to compute the of the subarray .

Can you write a program to help Dr. Henri?

Input Specification

The first line of input will contain two space-separated integers, and .
The second line of input will contain space-separated integers, .
The next lines will each contain three space-separated integers, , , and . It is guaranteed that and .

Output Specification

lines, where the line is the answer to the 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

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

Good Problem！

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

A similar problem which is a 20-pointer

• Rimuru  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.

• 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

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

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

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

Selective Cutting is pretty overrated tbh