Современные компьютеры зацикливаются в десятки раз эффективнее человека
Рекламный проспект OS Vista-N
Перед возвращением в штаб-квартиру корпорации Аазу и Скиву пришлось заполнить на местной таможне декларацию о доходах за время визита. Получилась довольно внушительная последовательность чисел. Обработка этой последовательности заняла весьма долгое время.
— Своппер кривой, — со знанием дела сказал таможенник.
— А что такое своппер? — спросил любопытный Скив.
Ааз объяснил, что своппер — это структура данных, которая умеет делать следующее.
Учитывая, что обсчёт может затянуться надолго, корпорация «МИФ» попросила Вас решить проблему со своппером и промоделировать ЭТО эффективно.
Во входном файле заданы один или несколько тестов.
В первой строке каждого теста
записаны число \(N\) — длина последовательности и число \(M\) — число
операций (\(1 \le N, \, M \le 100\,000\)).
Во второй строке теста содержится \(N\) целых чисел,
не превосходящих \(10^6\) по модулю — сама последовательность.
Далее следуют \(M\) строк — запросы в формате 1 \(x_i\) \(y_i\) — запрос
первого типа, и 2 \(a_i\) \(b_i\) — запрос второго типа.
Сумма всех \(N\) и \(M\) по всему файлу не превосходит \(200\,000\).
Файл завершается строкой из двух нулей. Гарантируется, что \(x_i \le y_i\), а
\(a_i \le b_i\).
Для каждого теста выведите ответы на запросы второго типа, как показано в примере. Разделяйте ответы на тесты пустой строкой.
5 5 1 2 3 4 5 1 2 5 2 2 4 1 1 4 2 1 3 2 4 4 5 5 1 2 3 4 5 1 2 5 2 2 4 1 1 4 2 1 3 2 4 4 0 0
Swapper 1: 10 9 2 Swapper 2: 10 9 2
Компания Giggle открывает свой новый офис в Судиславле, и вы приглашены на собеседование. Ваша задача — решить поставленную задачу.
Вам нужно создать структуру данных, которая представляет из себя массив целых чисел. Изначально массив пуст. Вам нужно поддерживать две операции:
? i j» — возвращает минимальный
элемент между \(i\)-ым и \(j\)-м, включительно;
+ i x» — добавить элемент \(x\) после \(i\)-го
элемента списка. Если \(i = 0\), то элемент добавляется в начало
массива.
Конечно, эта структура должна быть достаточно хорошей.
Первая строка входного файла содержит единственное целое число \(n\) — число операций над массивом (\(1 \le n \le 200\,000\)). Следующие \(n\) строк описывают сами операции. Все операции добавления являются корректными. Все числа, хранящиеся в массиве, по модулю не превосходят \(10^9\).
Для каждой операции в отдельной строке выведите её результат.
Комментарий к примеру тестов.
Нижеследующая таблица показывает процесс изменения массива из примера.
| Операция | Массив после её выполнения |
| изначально | пуст |
+ 0 5 | 5 |
+ 1 3 | 5, 3 |
+ 1 4 | 5, 4, 3 |
+ 0 2 | 2, 5, 4, 3 |
+ 4 1 | 2, 5, 4, 3, 1 |
8 + 0 5 + 1 3 + 1 4 ? 1 2 + 0 2 ? 2 4 + 4 1 ? 3 5
4 3 1
Капрал Питуца любит командовать своим отрядом. Его любимый приказ «в начало строя». Он выстраивает свой отряд в шеренгу и оглашает последовательность приказов. Каждая приказ имеет вид «Солдаты с \(l_i\) по \(r_i\) — в начало строя!»
Пронумеруем солдат в начальном положении с 1 до \(n\), слева направо. Приказ «Солдаты с \(l_i\) по \(r_i\) — в начало строя!» означает, что солдаты, стоящие с \(l_i\) по \(r_i\) включительно, перемещаются в начало строя, сохраняя относительный порядок.
Например, если в некоторый момент солдаты стоят в порядке \(2, 3, 6, 1, 5, 4\), после приказа: «Солдаты с \(2\) по \(4\) — в начало строя!» порядок будет \(3, 6, 1, 2, 5, 4\).
По данной последовательности приказов найти конечный порядок солдат в строю.
В первой строке два целых числа \(n\) and \(m\) (\(2 \le n \le 100\,000\), \(1 \le m \le 100\,000\)) — количество солдат и количество приказов. Следующие \(m\) строк содержат по два целых числа \(l_i\) и \(r_i\) (\(1 \le l_i \le r_i \le n\)).
Выведите \(n\) целых чисел — порядок солдат в конечном положении после выполнения всех приказов.
6 3 2 4 3 5 2 2
1 4 5 2 3 6
Секретный бункер уходит на N этажей вниз. Под нижним этажом бункера находится сверхсекретная лаборатория. Злобный диверсант хочет вывести лабораторию из строя, залив её водой (даже очень небольшого количества воды хватит, чтобы запоганить сверхточные приборы). Для этого он использует лужицы воды, остающиеся от жизнедеятельности обитателей бункера. В лужицах i-го этажа находится Ei воды. Диверсанту известно, что если на нём скопится больше Сi воды, то перегородка не выдержит и вся вода сольется на этаж ниже. Он может проделать отверстия в некоторых перегородках, по которым вода также стечет вниз. Проделать отверстие в полу i-го этажа стоит Pi у.е. Помогите диверсанту уничтожить лабораторию с минимальными материальными затратами.
Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 500000) - количество этажей в бункере, в следующих N строках находятся тройки целых чисел Ci, Ei, Pi (0 < Ei ≤ Ci < 1000000; E1+E2+...+EN < 2000000000; Pi > 0; P1+P2+...+PN < 2000000000). Этажи нумеруются сверху вниз.
В первой строке выходного файла выдать количество денег, которое придется потратить злобному диверсанту, в следующих строках выведите номера этажей, в полу которых следует проделать отверстия.
4 1 1 1 1 1 3 3 1 2 3 1 10
3 1 3
Недавно разведка перехватила зашифрованное сообщение — строку s. Все ресурсы аналитического центра, в котором вы работаете, были брошены на его декодирование. Ваш отдел занимается шифрами нового поколения. На данный момент известно всего n таких шифров. Для каждого из них есть три характерных параметра — целые числа l, r и строка t. Пусть строка g была получена в результате применения этого метода. Тогда строка glgl+1 . . . gr−1gr (здесь gi — это i-й символ строки g) содержит t как подстроку.
Вам поручено определить для каждого типа шифрования, могло ли сообщение s быть получено в результате его применения.
Первая строка входного файла содержит строку s (1 ≤ |s| ≤ 100 000, где |s| — длина строки s).
Вторая строка входного файла содержит целое число n — количество типов шифрования (1 ≤ n ≤ 100 000). Последующие nстрок содержат по два целых числа li, ri и строку ti, разделенные пробелами — характерные параметры i-го метода шифрования (1 ≤ li ≤ ri ≤ |s|).
Все строки состоят из строчных букв латинского алфавита. Суммарная длина всех ti не превосходит 100 000.
Выведите одну строку — для каждого типа шифрования «+», если сообщение s могло быть получено в результате его применения, или «-» в противном случае.
frommarsiam 3 6 10 i 2 11 am 1 9 human
++-