реши задачу В финал олимпиады этого года вышли две команды бобров – красные и синие. В команде красных есть n бобров, пронумерованных целыми числами от 1 до n , а в команде синих есть m бобров, пронумерованных целыми числами от 1 до m . Про каждого бобра

6 ноября 2025
Другое

Условие:

реши задачу В финал олимпиады этого года вышли две команды бобров – красные и синие. В команде красных есть n
бобров, пронумерованных целыми числами от 1
до n
, а в команде синих есть m
бобров, пронумерованных целыми числами от 1
до m
.

Про каждого бобра известно время, за которое он построит плотину, для бобра из команды красных под номером i
это время равняется ai
, а для бобра из команды синих под номером i
это время равняется bi
. Изначально все числа ai
и все числа bi
равняются нулю.

Финал олимпиады проводится следующим образом: по очереди проводятся поединки между двумя бобрами из разных команд, причем каждый бобер из команды красных сыграет с каждым бобром из команды синих. Поединок длится, пока оба бобра не построят свою плотину, таким образом, время поединка равняется максимальному из времен постройки плотины двумя бобрами.

Поступают q
запросов одного из двух видов:

1
i
x
(1≤i≤n
, 1≤x≤108
) — присвоить ai=x
,
2
i
x
(1≤i≤m
, 1≤x≤108
) — присвоить bi=x
.
После каждого запроса нужно вывести время, которое займет финал между командами красных и синих бобров.

Входные данные
Первая строка содержит три целых числа n
, m
и q
(1≤n,m,q≤200000
) — количество бобров в команде красных, количество бобров в команде синих, и количество запросов соответственно.

Следующие q
строк задают запросы в формате, описанном в условии задачи.

Выходные данные
После каждого запроса выведите время, которое займет финал между командами красных и синих бобров.

Пример
Входные данныеСкопировать
2 2 5
1 2 4
2 1 7
2 2 2
1 2 8
2 2 9
Выходные данныеСкопировать
8
18
20
25
33

Решение:

Для решения задачи, давайте разберем ее по шагам.

Шаг 1: Понимание задачи

У нас есть две команды бобров: красные и синие. Каждая команда имеет определенное количество бобров, и каждому бобру присвоено время, за которое он построит плотину. Мы будем обрабатывать запросы, которые обновляют время для конкретного бобра, и после каждого запроса нам нужно вычислить общее время, которое займет финал между командами.

Шаг 2: Определение структуры данных

Для хранения времени постройки плотины для красных и синих бобров мы можем использовать два массива:
- a для красных бобров
- b для синих бобров

Также нам нужно будет хранить максимальное время для каждого из массивов, чтобы быстро вычислять общее время после каждого запроса.

Шаг 3: Обработка запросов

Запросы могут быть двух типов:
1. 1 i x — обновляем время для красного бобра i на x.
2. 2 i x — обновляем время для синего бобра i на x.

После каждого запроса мы будем пересчитывать максимальное время для обеих команд и выводить сумму этих максимальных времен.

Шаг 4: Реализация алгоритма

Теперь давайте реализуем алгоритм:

1. Мы считываем количество бобров и количество запросов. 2. Инициализируем массивы и для хранения времен постройки. 3. Переменные и используются для хранения максимальных времен для красных и синих бобров соответственно. 4. В цикле обрабатываем каждый запрос: - Если запрос обновляет красного бобра, обновляем его время и пересчитываем максимальное время для красных. - Если запрос обновляет синего бобра, обновляем его время и пересчитываем максимальное время для синих. 5. После каждого запроса выводим сумму максимальных времен. Для входных данных: Вывод будет: Таким образом, мы успешно решили задачу.