agata_kristie.cpp

/*
Агата и Кристи

Кристи и Агата – лучшие подруги. Они любят проводить свободное время за разгадыванием головоломок. В этот раз загадку подготовила Кристи, помогите Агате справиться с задачей. Даны n чисел ai (1 <= ai <= 200000). Также имеются q запросов вида (lj , rj) – такой запрос означает, что надо сложить все числа на отрезке от lj до rj включительно и вернуть полученную сумму. Кристи дала Агате набор чисел и сами запросы. Задача Агаты – расставить числа ai на позициях от 1 до n (по одному на позицию) так, чтобы сумма ответов на все q запросов была как можно больше. Помогите Агате!

Формат входных данных
В первой строке через пробел даны количество чисел в наборе – n (1 <= n <= 200000) и количество запросов q (1 <= q <= 200000). Во второй строке даны числа ai (1 <= ai <= 200000), записанные через пробел. В следующих q строках даны запросы по одному в строке. Запрос j состоит из двух чисел lj и rj , записанных через пробел (1 <= lj <= rj <= n).

Формат выходных данных
Выведите единственное число – максимальную сумму ответов на запросы, которую может получить Агата.
Примеры
Вход:
5 3
1 9 4 3 1
1 4
2 2
3 5
Выход:
34

Вход:
1 1
5
1 1
Выход:
5

Вход:
2 2
8 4
1 1
2 2
Выход:
12

*/

#include <iostream>
#include <algorithm>

int main() {
    std::ios::sync_with_stdio(false);
    int n, q;
    std::cin >> n >> q;
    long long* array = new long long[n], *counter = new long long[n + 1];

    for (int i = 0; i < n; i++) {
        std::cin >> array[i];
        counter[i] = 0;
    }

    std::sort(array, array+n);

    counter[n] = 0;

    for (int i = 0, left, right; i < q; i++) {
        std::cin >> left >> right;
        counter[left - 1]++;
        counter[right]--;
    }

    long long currentTimes = 0;
    for (int i = 0; i < n; i++) {
        currentTimes += counter[i];
        counter[i] = currentTimes;
    }

    std::sort(counter, counter + n);

    long long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += counter[i] * array[i];
    }

    std::cout << sum;

    delete[] array;
    delete[] counter;
}