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 \leq N, Q \leq 4 000$
$1 \le A_i \le 10^9$ $1 \leq A_{i} \leq 10^{9}$

Subtask 2 [60%]

$1 \le N, Q \le 200\,000$ $1 \leq N, Q \leq 200 000$
$1 \le A_i \le 200\,000$ $1 \leq A_{i} \leq 200 000$

Subtask 3 [30%]

$1 \le N, Q \le 200\,000$ $1 \leq N, Q \leq 200 000$
$1 \le A_i \le 10^9$ $1 \leq A_{i} \leq 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 \leq l_{i} \leq r_{i} \leq N$ and $1 \le k_i \le 10^9$ $1 \leq k_{i} \leq 10^{9}$ .

Output Specification

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

Sample Input 1

Copy

Sample Output 1

Copy

Sample Input 2

Copy

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

Copy

Comments

5

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

A similar problem which is a 12-pointer