#113620

Проверка автомата

Источники: [ Личные олимпиады, Турнир Архимеда, 2017, Задача J ]

Андрюша — юный инженер. Сейчас он конструирует современный автомат для преобразования чисел. В процессе конструирования к автомату добавляются все новые и новые блоки, и Андрюше интересно, как будет работать автомат после каждой такой модификации.

Автомат представляет собой последовательность из блоков двух типов: максимизаторов и минимизаторов . На каждом блоке написано некоторое натуральное число x . Максимизатор принимает на вход натуральное число a и подает на выход число max ( x , a ) . Минимизатор принимает на вход натуральное число a и подает на выход число min ( x , a ) .

Автомат работает следующим образом: он принимает некоторое натуральное число, которые подает на вход первому блоку, затем то, что получилось на выходе у первого блока, подается на вход второго блока, и так далее. В итоге автомат возвращает число, получившееся на выходе у последнего блока. Иначе говоря, автомат просто последовательно пропускает данное ему число через все блоки.

Изначально в автомате нет ни одного блока, и он просто возвращает число, которое принимает.

Андрюша последовательно выполняет действия с автоматом. Действия бывают трех типов:

Добавить в конец последовательности блоков автомата максимизатор, на котором написано число x .
Добавить в конец последовательности блоков автомата минимизатор, на котором написано число x .
Подать на вход автомату число x . В этом случае Андрюша хочет узнать, что автомат вернет на выход.

Андрюша уже запланировал, какие действия и в каком порядке он будет совершать. Напишите программу, которая определит результат работы автомата Андрюши, чтобы он мог убедиться в его исправности!

Входные данные

Первая строка входных данных содержит единственное целое число n ( 1 ≤ n ≤ 4·10 ⁵ ) — суммарное количество действий Андрюши.

В каждой из следующих n строк содержится по два целых числа t и x ( 1 ≤ t ≤ 3 , 1 ≤ x ≤ 10 ⁹ ), где t — это тип очередного действия. Если t = 1 , то Андрюша хочет добавить к автомату максимизатор, на котором написано число x . Если t = 2 , то Андрюша хочет добавить к автомату минимизатор, на котором написано число x . Если t = 3 , то Андрюша хочет подать на вход автомату число x и узнать, что получится на выходе.

Выходные данные

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

Примеры

Входные данные

Выходные данные

#114062

Двусторонний ток

Источники: [ Личные олимпиады, Baltic Olympiad in Informatics, Baltic Olympiad in Informatics 2018, Двусторонний ток ]

Фредерик играет с игрушечной железной дорогой, которую он сам сделал, чем очень гордится. Дорога состоит из $N$ сегментов путей, соединённых по кругу, и пронумерованных $1,2,\dots,N$ по часовой стрелке. Электричество подается локомотиву через M проводов, проложенных арками вдоль круга. Через каждый сегмент дороги проложен как минимум один провод.

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

По каждому проводу, проложенному вдоль путей, ток может течь в одном направлении – либо по часовой, либо против часовой стрелки, причем Фредерик может выбирать направление на своё усмотрение. Двусторонний ток можно получить, если подвести к сегменту ток и в одном, и в другом направлении (по двум разным проводам).

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

Входные данные

На первой строке даны два целых числа $N$ и $M$ – количество сегментов железной дороги и количество проводов, соответственно.

На каждой из следующих $M$ строк даны два числа $1 \le a, b \le N$, указывающих, что имеется провод, покрывающий сегменты $a, a+1, \dots , b$. Если $b$ меньше $a$, это значит что последовательность сегментов перескакивает через $N$, т.е. покрываются $a, \dots , N, 1, \dots , b$. $a=b$, то провод покрывает только один сегмент.

Выходные данные

На единственной строке вывести последовательность символов длиной $M$, состоящую из знаков 0 или 1. $i$-тый символ должен быть равен 0, если ток в $i$-том проводе нужно направить по часовой стрелке, и 1, если ток нужно направить против часовой стрелки. Если существует несколько решений, вывести любое из них. Если решений нет, вывести текст "impossible".

Система оценки

Тесты разделены на группы. Очки за группу даются только если корректно решены все тесты в группе.

Группа Очки Ограничения Дополнительные ограничения

1. [13] $2\leq N,M\leq 15$

2. [20] $2\leq N,M\leq 100$

3. [22] $2\leq N,M\leq 1000$

4. [19] $2\leq N,M\leq 100000$ Нет проводов с b<a.

5. [26] $2\leq N,M\leq 100000$

Примеры

Входные данные

Выходные данные

Входные данные

Выходные данные

impossible

Входные данные

5 2
1 5
3 3

Выходные данные

impossible

Входные данные

Выходные данные

#114080

Глобальное потепление

Источники: [ Личные олимпиады, Central European Olympiad in Informatics , Central European Olympiad in Informatics 2018, Глобальное потепление ]

Глобальное потепление — это важная проблема, и Джонни знает об этом. Он решил проанализировать историю температур и найти подпоследовательной дней (не обязательно последовательных), в которой температура строго возрастает. Это убедит неверующих!

Джонни нашёл исторические данные за $n$ последовательных дней. Температура в $i$-й день была $t_i$.

Формально, нам интересно найти длину наибольшей возрастающей подпоследовательности (НВП) последовательности $(t_1, t_2, \ldots, t_n)$, то есть наибольшее такое $k$, что возможно выбрать возрастающую последовательность индексов $1 \leq a_1 lt a_2 \lt \ldots \lt a_k \leq n$, для которой $t_{a_1} \lt t_{a_2} \lt \ldots \lt t_{a_k}$.

Джонни хочет найти действительно длинную подпоследовательность, а поэтому он решил сжульничать. Сначала он выберет непустой отрезок дней и целое число $d$ ($-x \leq d \leq x$), а затем увеличит температуру в каждый из этих дней на $d$. Такое небольшое изменение, вероятно, не будет обнаружено обществом, но при этом оно может сделать длину НВП больше. Разрешено выбирать $d = 0$.

Какая максимально возможная длина НВП после такого изменения?

Входные данные

Первая строка содержит два целых числа $n$ и $x$ ($1 \leq n \leq 2 \cdot 10 ^ 5$, $0 \leq x \leq 10 ^ 9$) — количество дней и ограничение на модуль числа $d$.

Вторая строка содержит $n$ целых чисел $t_1, t_2, \ldots, t_n$ ($1 \leq t_i \leq 10 ^ 9$) — последовательность исторических температур.

Выходные данные

Выведите одно целое число — максимально возможную длину НВП после одного изменения.

Система оценки

$\text{[math]}$

Примечание

В примере из условия Джонни может выбрать отрезок $[2; 3]$ и $d = -5$, что означает уменьшение $t_2$ и $t_3$ на 5. Тогда новая последовательность — это $(7, -2, 0, 12, 2, 7, 3, 4)$, в которой можно найти НВП $(-2, 0, 2, 3, 4)$ длины $5$.

Примеры

Входные данные

8 10
7 3 5 12 2 7 3 4

Выходные данные

#114081

Лотерея

Источники: [ Личные олимпиады, Central European Olympiad in Informatics , Central European Olympiad in Informatics 2018, Лотерея ]

Обратите внимание на нестандартное ограничение по памяти.

Уже долгое время вы — фанат Байтлото. Примерно столько же времени ваши родственники говорят вам, что все такие игры — это пустая трата денег. Вы уверены, что это так из-за их неумения играть! У вас есть идеальный план, и скоро все увидят, как вы выигрываете.

Есть много типов игр. Вы интересуетесь в одном из них: Битлото. Выбор был прост, так как это самый простой из предлагаемых типов игр: каждый день случайно выпадает ровно одно число. Вы записываете эти числа за $n$ последовательных дней и получаете последовательность $a_1, a_2, \ldots, a_n$. Вы уверены, что в этой последовательности есть какая-то закономерность, а именно, в отрезках из $l$ последовательных дней. Ваша семья всё ещё не верит вам, так что единственный способ убедить их — это использовать серьёзную математику.

Есть $n - l + 1$ отрезок дней длины $l$. $i$-й отрезок начинается в позиции $i$ и содержит элементы $a_i, a_{i + 1}, \ldots, a_{i + l - 1}$. Расстояние между двумя отрезками — это количество несовпадающих элементов на соответствующих позициях. Другими словами, для отрезков $x$ и $y$ это количество таких $i$ ($0 \leq i < l$), что $a_{x + i}$ и $a_{y + i}$ различны. И наконец, будем говорить, что два отрезка $k$-похожи, если расстояние между ними не превосходит $k$.

Зафиксированы последовательность и число $l$. Вам даны $q$ запросов. В каждом запросе вам дано число $k_j$ и для каждого из $n - l + 1$ отрезов вы должны найти количество отрезков той же длины, которые $k$-похожи на данный (не считая сам этот отрезок).

Входные данные

Первая строка содержит два целых числа $n$ и $l$ ($1 \leq l \leq n \leq 10000$) — количество дней и длину анализируемых отрезков.

Вторая строка содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10 ^ 9$), где $a_i$— число, выпавшее в $i$-й день.

Третья строка содержит целое число $q$ ($1 \leq q \leq 100$) — количество запросов.

Каждая из следующих $q$ строк содержит целое число $k_j$ ($0 \leq k_j \leq l$) — параметр похожести для $j$-го запроса.

Выходные данные

Выведите $q$ строк. $j$-я строка должна содержать $n - l + 1$ целых чисел, являющихся ответами на $j$-й запрос. $i$-е число в строке должно являться количеством других отрезков, которые $k_j$-похожи на $i$-й отрезок.

Система оценки

$\text{[math]}$

Примечание

Пояснение к примеру из условия: в примере есть пять отрезков длины $2$:

первый содержит числа $1$ $2$
второй содержит числа $2$ $1$
третий содержит числа $1$ $3$
четвёртый содержит числа $3$ $2$
пятый содержит числа $2$ $1$

Есть два запроса.

В первом запросе $k=1$. Первый и ттретий отрезки отличаются только во второй позиции, поэтому расстояние между ними равно $1$. Первый и четвёртый отрезки отличаются только в первой позиции, поэтому расстояние между ними равно $1$. Это единственные два отрезка, которые $1$-похожи на первый отрезок, поэтому первое выведенное число равно $2$.

Во втором запросе $k=2$. Все пары отрезков $2$-похожи.

Примеры

Входные данные

6 2
1 2 1 3 2 1
2
1
2

Выходные данные

2 1 1 1 1 
4 4 4 4 4

#114082

Облачные вычисления

Источники: [ Личные олимпиады, Central European Olympiad in Informatics , Central European Olympiad in Informatics 2018, Облачные вычисления ]

Джонни основывает Bytecomp — компанию, которая предлагает вычислительные мощности в облаке. Компании этого профиля обычно обладают большим количеством быстрых компьютеров, на которых производятся вычислениях их клиентов.

Джонни ещё не купил ни одного компьютера. Он пошёл в компьютерный магазин и получил список из $n$ доступных компьютеров. Каждый компьютер характеризуется колиеством процессорных ядер $c_i$, частотой $f_i$ и ценой $v_i$. Такой компьютер имеет $c_i$ независимых ядер, не мешающих друг другу, поэтому они могут быть назначены для выполнения разных задач.

Когда клиент делает заказ на ресурс, он определяет требуемое количество ядер $C_j$ и минимальную необходимую частоту $F_j$. Также заказ содержит цену $V_j$, которую клиент собирается заплатить. Если заказ принимается, Bytecomp должна предоставить эксклюзивный доступ к вычислительным мощностям, требуемым клиентом. Джонни должен выбрать $C_j$ ядер (возможно, из разных компьютеров), каждое частотой хотя бы $F_j$. Эти ядра не могут быть назначены какому-нибудь другому заказу.

Помогите Джонни заработать так много денег, как это возможно: выберите оптимальное подмножество заказов для исполнения, а также подмножество компьютеров из магазина, чтобы удовлетворить все принятые заказы. Ваша цель — максимизировать итоговую прибыль, то есть разность между доходом от предоставления вычислительных ресурсов клиентам и стоимостью покупки компьютеров.

Входные данные

Первая строка содержит целое число $n$ ($1 \leq n \leq 2000$) — количество компьютеров, доступных в магазине.

Каждая из следующих $n$ строк содержит описание одного компьютера. Она содержит три целых числа $c_i$, $f_i$ и $v_i$ ($1 \leq c_i \leq 50$, $1 \leq f_i \leq 10^9$, $1 \leq v_i \leq 10 ^ 9$) — количество ядер, частота и цена, соответственно.

Следующая строка содержит целое число $m$ ($1 \leq m \leq 2000$) — количество заказов.

Каждая из следующих $m$ строк содержит описание одного заказа. Она содержит три целых числа $C_j$, $F_j$ и $V_j$ ($1 \leq C_j \leq 50$, $1 \leq F_j \leq 10^9$, $1 \leq V_j \leq 10^9$) — количество запрашиваемых ядер, минимальная разрешённая частота и бюджет клиента, соответственно.

Выходные данные

Выведите единственное целое число — максимально возможную итоговую прибыль.

Система оценки

$\text{[math]}$

Примечание

Пояснение к примеру из условия: есть четыре доступных типа компьютера и три заказа. Оптимально купить четырехъядерные компьютеры стоимостью $700$ и $750$ ($1450$ в сумме) и затем принять первые два заказа, получив $300 + 1500 = 1800$. Тогда у нас есть четыре ядра с частотой $2000$ и четыре ядра с частотой $2200$. Мы можем назначить любые шесть из них второму клиенту (требуемая частота $1900$) и одно — второму клиенту (требуемая частота $1500$). Одно ядро не будет использоваться, что разрешено.

Итоговая прибыль равна $1800 - 1450 = 350$.

Примеры

Входные данные

4
4 2200 700
2 1800 10
20 2550 9999
4 2000 750
3
1 1500 300
6 1900 1500
3 2400 4550

Выходные данные