Little Girl and Maximum Sum (Codeforces 276C)
Tags: Implement, data structures

The little girl loves the problems on array queries very much.One day she came across a rather well-known problem: you've got an array of $$$n$$$ elements (the elements of the array are indexed starting from 1); also, there are $$$q$$$ queries, each one is defined by a pair of integers $$$l_i$$$, $$$r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$. You need to find for each query the sum of elements of the array with indexes from $$$l_i$$$ to $$$r_i$$$, inclusive.The little girl found the problem rather boring. She decided to reorder the array elements before replying to the queries in a way that makes the sum of query replies maximum possible. Your task is to find the value of this maximum sum.

Input: The first line contains two space-separated integers $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) and $$$q$$$ ($$$1 \le q \le 2\cdot10^5$$$) — the number of elements in the array and the number of queries, correspondingly.The next line contains $$$n$$$ space-separated integers $$$a_i$$$ ($$$1 \le a_i \le 2\cdot10^5$$$) — the array elements.Each of the following $$$q$$$ lines contains two space-separated integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the $$$i$$$-th query.

Output: In a single line print, a single integer — the maximum sum of query replies after the array elements are reordered.Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.


Sample Inputs:
3 3
5 3 2
1 2
2 3
1 3

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

Sample Outputs:
25

33

Solution (Python):
import sys
input = sys.stdin.readline
t = 1
for _ in range(t):
    (n, q) = map(int, input().split())
    a = sorted(list(map(int, input().split())), reverse=True)
    l = [0] * (n + 1)
    for i in range(q):
        (li, ri) = map(int, input().split())
        l[li - 1] += 1
        l[ri] -= 1
    for i in range(1, n + 1):
        l[i] += l[i - 1]
    l.sort(reverse=True)
    ans = 0
    for i in range(n):
        ans += a[i] * l[i]
    print(ans)

Solution (Python):
import sys
from sys import stdin, stdout
from collections import defaultdict, Counter, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right

def ints():
    return map(int, sys.stdin.readline().strip().split())

def li():
    return list(map(int, sys.stdin.readline().strip().split()))

def string():
    return sys.stdin.readline().strip()

def get_int():
    return int(sys.stdin.readline().strip())

def li_strings():
    return list(map(str, sys.stdin.readline().strip().split()))

def primeFactors(n):
    i = 2
    primfac = []
    while i * i <= n:
        while n % i == 0:
            primfac.append(i)
            n = n / i
        i = i + 1
    if n > 1:
        primfac.append(int(n))
    return primfac

def prime_sieve(n):
    is_prime = [True for _ in range(n + 1)]
    is_prime[0] = is_prime[1] = False
    i = 2
    while i * i <= n:
        if is_prime[i]:
            j = i * i
            while j <= n:
                is_prime[j] = False
                j += i
        i += 1
    return is_prime

def find_divisors(number):
    divisors = []
    for i in range(1, int(number ** 0.5) + 1):
        if number % i == 0:
            divisors.append(i)
            if i != number // i:
                divisors.append(number // i)
    return divisors

def solve():
    (n, q) = ints()
    nums = li()
    line = [0] * (n + 2)
    for _ in range(q):
        (x, y) = ints()
        line[x] += 1
        line[y + 1] -= 1
    for i in range(1, len(line)):
        line[i] += line[i - 1]
    line.sort()
    nums.sort()
    ans = 0
    for i in range(n):
        ans += line[i + 2] * nums[i]
    return ans
if __name__ == '__main__':
    for _ in range(1):
        print(solve())

Solution (Python):
import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [0] * (n + 2)

def insert(l, r):
    b[l] += 1
    b[r + 1] -= 1
for _ in range(q):
    (l, r) = map(int, input().split())
    insert(l, r)
for i in range(1, n + 1):
    b[i] = b[i - 1] + b[i]
b.pop()
b.sort()
a.sort()
ans = 0
for i in range(1, n + 1):
    ans += a[i] * b[i]
print(ans)