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

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

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$ ~N~ data points: $A_1, A_2, \dots, A_N$ ~A_1, A_2, \dots, A_N~, and has defined the $k$ ~k~-interest of a subarray as the sum of all numbers greater than or equal to $k$ ~k~ minus the sum of all numbers less than $k$ ~k~.

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

Dr. Henri knows that some of the data might be outliers, so he asks you $Q$ ~Q~ queries of the form l r k, asking you to compute the $k$ ~k~-interest of the subarray $A_l, A_{l+1}, \dots, A_r$ ~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 N, Q \le 4\,000~
$1 \le A_i \le 10^9$ ~1 \le A_i \le 10^9~

Subtask 2 [60%]

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

Subtask 3 [30%]

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

Input Specification

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

Output Specification

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

Sample Input 1

Sample Output 1

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

Comments

5

1419903188 commented on Dec. 13, 2018, 12:52 p.m.

A similar problem which is a 20-pointer

-13

Rimuru commented on Dec. 14, 2018, 4:34 p.m. ← edit 3 →

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

This comment is hidden due to too much negative feedback. Show it anyway.

10

whomax commented on Dec. 14, 2018, 8:24 p.m.

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

-9

Rimuru commented on Dec. 14, 2018, 10: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.

This comment is hidden due to too much negative feedback. Show it anyway.

-9

imathblue commented on Dec. 14, 2018, 3:32 a.m.

Selective Cutting is pretty overrated tbh

This comment is hidden due to too much negative feedback. Show it anyway.