Equalizing Pillars

Peregrine_Falcon Criterion 2021 Round 8
Limits 1s, 1.0 GB

There are $N$ pillars made of bricks. The height of each pillar is the number of bricks in that pillar.

In this problem, you have to answer $Q$ independent queries on these pillars. For each query, you will be given a range $L$ and $R$. You have to find out the minimum number of moves to make all the pillars equal in height within the range of $L$ and $R$.

In one move, you can add or remove a single brick from a pillar within the range.


The first line of the input will contain two space-separated integers $N$ and $Q (1 \leq N, Q \leq 10^5)$, the number of pillars and the number of queries, respectively.

The next line will contain $N$ space-separated integers, $i^{\text{th}}$ integer denoting the height of $i^{\text{th}}$ pillar. The heights will be in range $[1, 10^9]$.

The next $Q$ lines will describe the queries. For each query, you will be given two space-separated integers $L$ and $R (1 \leq L \leq R \leq N)$, the range to be considered for the query.


For each query, print the answer in a line in the same order in which the queries appear in the input.


5 3
1 6 2 3 5
2 4
1 5
4 4

Explanation of the first query:

We have numbers 6, 2, and 3.
If we want to make all of them equal to 4, we have to decrease value 6 twice, increase value 2 twice, and the value 3 once. Hence, we need 5 moves.
If we want to make all of them equal to 3, we have to decrease value 6 thrice, and increase value 2 once. Here, we need a total of 4 moves.
So the optimal answer will be 4 moves.


Login to submit.


49% Solution Ratio
solaimanopeEarliest, Jan '21
nusuBotFastest, 0.1s
Nasif_44thLightest, 12 MB
mh755628Shortest, 1622B
Toph uses cookies. By continuing you agree to our Cookie Policy.