Задача 4: Агата и Кристи

@Aksolot · Регистрация: 12.09.2021

Студворк — интернет-сервис помощи студентам

Задача 4: Агата и Кристи
Кристи и Агата – лучшие подруги. Они любят проводить свободное время за разгадыванием головоломок. В этот раз загадку подготовила Кристи, помогите Агате справиться с задачей.
Даны n чисел ai (1≤ai≤2⋅10⁵). Также имеются q запросов вида (lj,rj) – такой запрос означает, что надо сложить все числа на отрезке от lj до rj включительно и вернуть полученную сумму. Кристи дала Агате набор чисел и сами запросы. Задача Агаты – расставить числа ai на позициях от 1 до n (по одному на позицию) так, чтобы сумма ответов на все q запросов была как можно больше.

Помогите Агате!

Формат входных данных
В первой строке через пробел даны количество чисел в наборе – n (1≤n≤2⋅10⁵) и количество запросов q (1≤q≤2⋅10⁵).Во второй строке даны числа ai (1≤ai≤2⋅10⁵), записанные через пробел.
В следующих q строках даны запросы по одному в строке. Запрос j состоит из двух чисел lj и rj, записанных через пробел (1≤lj≤rj≤2⋅10⁵).
Формат результата
Выведите единственное число – максимальную сумму ответов на запросы, которую может получить Агата.

Примеры
Входные данные
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

@eaa · 10.01.2022, 16:50

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
from itertools import accumulate
 
n, q = map(int, input().split())
*a, = map(int, input().split())
 
d = [0] * n
for _ in range(q):
    left, right = map(int, input().split())
    d[left - 1] += 1
    if right < n:
        d[right] -= 1
 
print(sum(x * y for x, y in zip(sorted(a), sorted(accumulate(d)))))

пусть останется тут, может еще где "всплывёт" эта задача.

Новые блоги и статьи Все статьи Все блоги /
интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .
Где деньги лежат kumehtar 02.07.2026 Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .	Krabik для WoW 3.3.5a, многоязычный AmbA 02.07.2026 Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .	Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .	сукцессия 16. Общий обзор, в основном что бы другие ии поняли anaschu 29.06.2026 # Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .

@Aksolot 0 / 0 / 0 Регистрация: 12.09.2021 Сообщений: 7

	Задача 4: Агата и Кристи 12.09.2021, 15:11. Показов 3235. Ответов 20 Метки нет (Все метки) Задача 4: Агата и Кристи Кристи и Агата – лучшие подруги. Они любят проводить свободное время за разгадыванием головоломок. В этот раз загадку подготовила Кристи, помогите Агате справиться с задачей. Даны n чисел ai (1≤ai≤2⋅10⁵). Также имеются q запросов вида (lj,rj) – такой запрос означает, что надо сложить все числа на отрезке от lj до rj включительно и вернуть полученную сумму. Кристи дала Агате набор чисел и сами запросы. Задача Агаты – расставить числа ai на позициях от 1 до n (по одному на позицию) так, чтобы сумма ответов на все q запросов была как можно больше. Помогите Агате! Формат входных данных В первой строке через пробел даны количество чисел в наборе – n (1≤n≤2⋅10⁵) и количество запросов q (1≤q≤2⋅10⁵).Во второй строке даны числа ai (1≤ai≤2⋅10⁵), записанные через пробел. В следующих q строках даны запросы по одному в строке. Запрос j состоит из двух чисел lj и rj, записанных через пробел (1≤lj≤rj≤2⋅10⁵). Формат результата Выведите единственное число – максимальную сумму ответов на запросы, которую может получить Агата. Примеры Входные данные 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 0