Alice and Queries
Practice
4.5 (2 votes)
Sorting
Implementation
Data structures
Easy
Segment tree
Bit
Approved
Problem
49% Success 962 Attempts 20 Points 1s Time Limit 256MB Memory 1024 KB Max Code

Alice is having an array of N numbers (1-based indexing) and was playing with it by answering queries of the form \( L,R \) where \( 1 \le L \le R \le N \). Query was simply sum of elements of the array with indexes from \( L to R \) (Both inclusive).

In the mean time John, her younger brother came and rearrange all the elements of the array before she could reply to the queries.

Now if earlier the output of queries were \( Q[1],Q[2]... \) Now it becomes \( Q'[1],Q'[2]... \)

The values of \( Q'[1],Q'[2]... \) may still be same. But one thing good happen in all this incidence is the sum of all the queries become maximum that is \( Q'[1]+Q'[2]+... \) is maximum . She is interested in finding this maximum value of sum.

Input Format:
First line consists of N integers and each q queries. Next line contains N elements presented in array. After this, the line consists of q queries, where each query is of form \( L,R \).

Output Format:
We need to find the maximum sum of query replies after the array elements are rearranged .

Constraints :

\( 1 \le N \le 10^{5} \) \( 1 \le q \le 10^{5} \)

Each array element is in range between \( 1 to 2·10^{5} \)

Each query satisfies \( 1 \le L \le R \le N \)

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
10 votes
Tags:
MathPrefixBasic MathBasic ProgrammingDynamic Programming
Points:20
5 votes
Tags:
MathematicsOpenEasyMathematicsMathamatics
Points:30
7 votes
Tags:
MathematicsDynamic ProgrammingEasy-Medium