--->
90 задач
<---
Источники
Секретная корпорация, занимающаяся поиском инопланетных жизненных форм обнаружила на одной из планет созвездия Альфа удивительные живые организмы (даже не плоские, а одномерные). Она приняла решение вести наблюдение за развитием и изменением численности организмов, с этой целью на орбиту планеты был послан спутник - наблюдатель, который мог следить за изменениями численности организмов. Недостаток этого "наблюдателя" в том, что он может отслеживать изменения только на той территории планеты, которая находиться непосредственно под ним.
С этой целью его траектория была разбита на равные интервалы. Они пронумерованы от 1 до N. По запросу с Земли о количестве живых форм в интервале с L по R (L ≤ R) - спутник должен, пролетая над ними (L, L+1, …,R-1, R интервалами) произвести подсчет и затем, в ответ на запрос, отправить полученные данные. Но количество организмов постоянно изменяется: в некоторое время в X интервале на Y единиц.
Помогите написать программу для спутника, которая будет отвечать на запросы и отслеживать количество единиц жизни в каждом интервале.
Формат входных данных
Во входном файле первым записано число N (1 ≤ N ≤ 213 = 8192). Затем записана последовательность событий:
| Событие | Параметры | Описание |
| 1 | X, Y | Изменение количества организмов в интервале с номером X на Y единиц.(-215 ≤ Y ≤ 215-1 = 32767) |
| 2 | L, R | Запрос суммарного количества организмов с L по R интервал. |
| 0 |
| Завершение работы. |
Количество событий не превосходит 100000.
Формат выходных данных
В выходной файл записывать только ответы на запросы.
Примеры
| Входные данные | Выходные данные |
| 2 1 1 4 2 1 1 2 1 1 0 | 4 4
|
| 4 2 1 4 1 1 3 1 4 2 2 2 4 2 1 2 1 4 -2 1 2 8 2 1 4 0 | 0 2 3 11
|
В 2050 году руководство Глобальной Телефонной Сети (ГТС) приняло решение о новой системе тарификации коротких текстовых сообщений. Теперь цена отправки одного сообщения зависит от количества совпадающих цифр в начале номеров телефонов отправителя и получателя. Если первые \(c\) цифр телефонов совпадают, а \((c+1)\)-я цифра различается, то стоимость сообщения составляет \((10-c)\) кредитов (\(0\le c\le9\)). Все номера телефонов — десятизначные. При этом ГТС разрешает каждому абоненту отправлять сообщение только в пределах часового пояса своего проживания или часовых поясов, отличающихся от него на 1 час.
Школьник Поликарп из Ханты-Мансийска (время +2 часа от московского) успешно решил все задания первого тура олимпиады школьников по информатике. Теперь он желает сообщить об этом в Париж (время −2 часа от московского) своему учителю — профессору де Коде́ру. Так как Ханты-Мансийск и Париж находятся не в соседних часовых поясах, Поликарп не может послать сообщение напрямую. Поэтому он пользуется тем, что у него есть друзья, которые проживают в Ханты-Мансийске, Париже, а также в промежуточных часовых поясах — в Дубае (время +1 час от московского), Москве и Калининграде (время −1 час от московского). Друзья Поликарпа по цепочке доставят профессору де Коде́ру столь важную информацию. Поликарп хочет организовать передачу информации таким образом, чтобы минимизировать суммарные расходы по отправке всех сообщений.
Напишите программу, определяющую цепочку доставки, для которой суммарная стоимость отправленных сообщений минимальна.
Первые две строки входного файла содержат телефонные номера Поликарпа и профессора де Коде́ра. Далее следуют 5 блоков данных, описывающих друзей Поликарпа, живущих в Ханты-Мансийске, Дубае, Москве, Калининграде и Париже, соответственно. Каждый блок начинается со строки, содержащей одно число \(n_i\) (\(1\le n_i\le100\,000\)) — количество друзей Поликарпа в соответствующем городе, после которой следуют \(n_i\) строк — номера телефонов друзей. Все номера телефонов состоят ровно из 10 цифр. Гарантируется, что сумма всех \(n_i\) не превосходит 100 000. Все номера телефонов во входных данных различны.
В первой строке выходного файла выведите минимальную возможную стоимость передачи информации \(w\) и количество задействованных в цепочке телефонных номеров \(k\). Далее выведите \(k\) номеров телефонов, описывающих саму цепочку, в порядке следования от Поликарпа к профессору де Коде́ру. Первый номер в цепочке должен совпадать с номером телефона Поликарпа, а последний — с номером телефона профессора де Коде́ра. Если решений несколько, выведите любое.
Система оценивания
2099013166 7043239909 1 0258442145 1 0000000000 1 0000000001 1 0000000002 1 0147571204
22 5 2099013166 0000000000 0000000001 0000000002 7043239909
4261802325 7967612531 1 8176476745 1 3084033164 1 1737248630 1 9447552231 1 2848478213
40 5 4261802325 3084033164 1737248630 9447552231 7967612531
У Олега есть матрица целых чисел \(N \times M\). Его очень часто просят узнать сумму всех элементов матрицы в прямоугольнике с левым верхним углом (\(x_1\), \(y_1\)) и правым нижним (\(x_2\), \(y_2\)). Помогите ему в этом.
В первой строке находится числа \(N, M\) размеры матрицы (\(1 \leq N, M \leq 1000\)) и K - количество запросов (\(1 \leq K \leq 100000\)). Каждая из следующих \(N\) строк содержит по \(M\) чисел --- элементы соответствующей строки матрицы (по модулю не превосходят 1000). Последующие K строк содержат по \(4\) целых числа, разделенных пробелом - \(x_1\) \(y_1\) \(x_2\) \(y_2\) --- запрос на сумму элементов матрице в прямоугольнике (\(1 \leq x_1 \leq x_2 \leq N, 1 \leq y_1 \leq y_2 \leq M\))
Для каждого запроса на отдельной строке выведите его результат - сумму всех чисел в элементов матрице в прямоугольнике \((x_1,y_1)\), \((x_2,y_2)\)
3 3 2 1 2 3 4 5 6 7 8 9 2 2 3 3 1 1 2 3
28 21
Секретный бункер уходит на 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
Сергей работает системным администратором в очень крупной компании. Естественно, в круг его обязанностей входит резервное копирование информации, хранящейся на различных серверах и «откат» к предыдущей версии в случае возникновения проблем.
В данный момент Сергей борется с проблемой недостатка места для хранения информации для восстановления. Он решил перенести часть информации на новые сервера. К сожалению, если что-то случится во время переноса, он не сможет произвести откат, поэтому процедура переноса должна быть тщательно спланирована.
На данный момент у Сергея хранятся \(n\) точек восстановления различных серверов, пронумерованных от 1 до \(n\). Точка восстановления с номером \(i\) позволяет произвести откат для сервера \(a_i\). Сергей решил разбить перенос на этапы, при этом на каждом этапе в случае возникновения проблем будут доступны точки восстановления с номерами \(l, l + 1, \ldots, r\) для некоторых \(l\) и \(r\).
Для того, чтобы спланировать перенос данных оптимальным образом, Сергею необходимо научиться отвечать на запросы: для заданного \(l\), при каком минимальном \(r\) в процессе переноса будут доступны точки восстановления не менее чем \(k\) различных серверов.
Помогите Сергею.
Первая строка входного файла содержит два целых числа \(n\) и \(m\) (\(1 \le n, m \le 10^5\)), разделенные пробелами — количество точек восстановления и количество серверов. Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) — номера серверов, которым соответствуют точки восстановления (\(1 \le a_i \le m\)).
Третья строка входного файла содержит \(q\) — количество запросов, которые необходимо обработать (\(1 \le q \le 100\,000\)). В процессе обработки запросов необходимо поддерживать число \(p\), исходно оно равно 0. Каждый запрос задается парой чисел \(x_i\) и \(y_i\), используйте их для получения данных запроса следующим образом: \(l_i = \left((x_i + p) \bmod n\right) + 1\),
\(k_i = \left((y_i + p) \bmod m\right) + 1\) (\(1 \le l_i,x_i \le n\), \(1\le k_i, y_i \le m\)). Пусть ответ на \(i\)-й запрос равен \(r\). После выполнения этого запроса, следует присвоить \(p\) значение \(r\).
На каждый запрос выведите одно число — искомое минимальное \(r\), либо 0, если такого \(r\) не существует.
7 3 1 2 1 3 1 2 1 4 7 3 7 1 7 1 2 2
1 4 0 6