DCP-523: Everything equal 2 Back to All Problems

Hard Data Structures > Segment Tree/Interval Tree


Professor Mahammad just created a large array using his brand-new true random number generator. However, he does not seem satisfied yet, especially after seeing many different numbers. That is why he came up with a new problem for you. He asks you to count the minimum number of moves to make the range of elements equal for each query. Here **move** denotes adding or subtracting 1 from any element in the range. Input: ------ The very first line of the input contains an integer **T (1 <=T <= 5)**, denoting the number of test cases. Each case consists of several lines. The first one contains two integers **N and Q (1 ≤ N, Q ≤ 5*10^4)** denoting the number of elements of the array and the number of queries respectively. The next line will contain **N** integers separated by spaces, denoting the elements of the array. Then there are **Q** lines each containing 2 space separated integers **1 <= l, r <= N** indicating the queries you need to process. **Each number in the input section is positive and not greater than 10^9.** Output: ------- For each test case, print **Q** lines, describing the minimum number of moves to make the range equal. **Note: Queries do not depend on each other. More formally, you are not required to update the elements of the array during queries.** Sample Input ------------ 1 5 5 1 3 2 4 5 1 3 2 2 1 5 4 5 3 5 Sample Output ------------- 2 0 6 1 3 Note: To equalize range [1, 3] we can change all numbers to 2 in (2 - 1) + (3 - 2) + (2 - 2) = 2 moves. To equalize range [2, 2] no moves are needed. To equalize range [3, 5] we can change all numbers to 4 in (4 - 2) + (4 - 4) + (5 - 4) = 3 moves.


Problem Setter:

Mahmud Allahverdiyev

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 4.00
C++ 4.00
C++14 4.00
C# 8.00
Go 8.00
Java 8.00
JavaScript 8.00
Objective-C 8.00
Perl 8.00
PHP 8.00
Python 8.00
Python3 8.00
Ruby 8.00
VB.Net 8.00

Problem Stats

20/81

Solve/Submission

Ranking

# User Language Timing
01 Robbinb1993 Cpp14 0.13s
02 mh755628 Cpp14 0.14s
03 tariqiitju Cpp14 0.21s
04 _c_k_r_ Cpp14 0.22s
05 mahbubcseju Cpp 0.29s
06 anik_JU Cpp 0.30s
07 Double_O Cpp14 0.33s
08 kzvd4729 Cpp14 0.39s
09 shahjalalshohag Cpp14 0.65s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support