Структуры данных

Твитнуть

Плюсануть

Класснуть

Запинить

Условие задачи Прогресс

ID 44054. Очередь с поддержкой минимума

Темы: Структуры данных

Реализуйте очередь с поддержкой минимума.

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

Первая строка входных данных содержит число N — количество операций с очередью (1≤N≤100000).
В каждой следующей строке содержится число a_i (0≤a_i≤10000). Если a_i>0,
то это число необходимо добавить в очередь. Если a_i=0, то это
запрос на удаление элемента из очереди.

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

На каждый запрос удаления элемента из очереди необходимо вывести значение
минимального элемента очереди (учитывая значение удаляемого элемента).
Если запрос удаления вызывается на пустой очереди, то необходимо вывести −1.

входные данные	выходные данные
9 5 4 3 6 0 0 0 0 0	3 3 3 6 -1

ID 30754. Поиск минимума с помощью приоритетной очереди

Темы: Куча Структуры данных

Дана последовательность чисел. Найти в ней наименьшее число.

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

Задано сначала число N (количество чисел в последовательности, 1<=N<=100000), а затем

N чисел.

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

Выведите наименьшее число.

Ввод	Вывод
7 4 2 5 -1 4 6 2	-1

ID 21888. Река

Темы: Структуры данных Двоичное дерево поиска Двоичное дерево поиска Двоичное дерево поиска Корневая оптимизация Декартово дерево

Во Флатландии протекает богатая рыбой река Большой Флат. Много лет назад река была поделена между n рыболовными предприятиями, каждое из которых получило непрерывный отрезок реки. При этом i-е предприятие, если рассматривать их по порядку, начиная от истока, изначально получило отрезок реки длиной ai .

С тех пор с рыболовными предприятиями во Флатландии k раз происходили различные события. Каждое из событий было одного из двух типов: банкротство некоторого предприятия или разделение некоторого предприятия на два.

При некоторых событиях отрезок реки, принадлежащий предприятию, с которым это событие происходит, делится на две части. Каждый такой отрезок имеет длину большую или равную 2. Деление происходит по следующему правилу. Если отрезок имеет четную длину, то он делится на две равные части. Иначе он делится на две части, длины которых различаются ровно на единицу, при этом часть, которая ближе к истоку реки, имеет меньшую длину.

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

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

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

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

Формат входного файла
Первая строка входного файла содержит два целых числа: n и p — исходное количество предприятий (2 ≤ n ≤ 100 000) и номер подзадачи (0 ≤ p ≤ 4). Вторая строка входного файла содержит n целых чисел a1, a2, …, an — длины исходных отрезков реки. Третья строка входного файла содержит целое число k — количество событий, происходивших с предприятиями (1 ≤ k ≤ 100 000). Последующие k строк содержат описания событий, i-я строка содержит два целых числа: ei и vi — тип события и номер предприятия, с которым оно произошло. Значение ei = 1 означает, что предприятие, которое после всех предыдущих событий является vi-м по порядку, если считать с единицы от истока реки, обанкротилось, а значение ei = 2 означает, что это предприятие разделилось на два. Гарантируется, что значение vi не превышает текущее количество предприятий. Гарантируется, что если отрезок предприятия при банкротстве или разделении требуется поделить на две части, то он имеет длину большую или равную 2. Гарантируется, что если на реке осталось единственное предприятие, оно не банкротится.

Формат выходного файла
Выходной файл должен содержать (k + 1) целых чисел, по одному в строке. Первая строка должна содержать исходную сумму квадратов длин отрезков реки, а каждая из последующих k строк — сумму квадратов длин отрезков реки после очередного события.

Пример
Ввод:
4 0
3 5 5 4
5
1 1
2 1
1 3
2 2
1 3
Вывод:
75
105
73
101
83
113

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

ID 21889. Чемпионат по поиску в сети Меганет

Темы: Структуры данных Строки Динамическое программирование Конструктив Задача на реализацию

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

Имя сервера представляет собой строку, содержащую от одной до пяти частей включительно. Каждая часть представляет собой непустую строку, состоящую из строчных букв латинского алфавита. Части разделены точкой. Примеры корректных имен сервера: «a», «ab.cd», «abacaba», «a.b.c.d.e».

Имя раздела представляет собой строку, которая может быть либо пустой, либо содержать от одной до пяти частей включительно. Каждая часть начинается с символа «/», после которого следует одна или несколько строчных латинских букв. Примеры корректных имен разделов: «», «/a», «/aba», «/a/b/c/d/e». Адрес формируется приписыванием имени раздела в конец имени сервера. Например, корректными адресами являются строки: «a», «aba/d/f/g/h», «a.b», «aba.caba/def/g», «c.d.e.f.g/a/b/c/d/e».

Для ограничения доступа к некоторым адресам сети Меганет организаторы чемпионата подготовили несколько фильтров. Фильтр, как и адрес, состоит из двух частей: фильтра сервера и фильтра раздела.

Фильтр сервера состоит из имени сервера, перед которым может также идти строка «*.». Если фильтр сервера представляет собой только имя сервера, то этому фильтру соответствует только сервер, имеющий точно такое же имя. Если фильтр сервера представляет собой строку «*.S », где S — имя сервера, то ему соответствуют сервера, удалением нуля или более начальных частей от имени которых можно получить строку S.

Аналогично, фильтр раздела представляет собой имя раздела, после которого может идти строка «/*». Фильтру раздела, который представляет собой просто имя раздела R, соответствуют только разделы, в точности совпадающие с R. Если фильтр раздела представляет собой строку «R/*», то ему соответствуют все разделы, удалением от имен которых нуля или более конечных частей можно получить строку R. Адрес соответствует фильтру, если его имя сервера соответствует фильтру сервера, а его имя раздела соответствует фильтру раздела.

Примеры фильтров и соответствующих им адресов приведены в таблице ниже.

ab.c/d/e	ab.c/d/e
*.a	a ax.a efg.a
*.a/b/c	a/b/c x.a/b/c e.fg.a/b/c
x.yz/a/*	x.yz/a x.yz/a/b/c x.yz/a/xyz
.a/	a x.a e.fg.a a/b/c x.a/ddd/c e.fg.a/b/c/g/haha/i
.a/b/c/	a/b/c x.a/b/c e.fg.a/b/c a/b/c/xxx e.fg.a/b/c/d/e/f

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

Пример:
Ввод:
2 0
a.bb/c
bb/c/d
4
a.bb
bb/c/d
a.bb/c/d
bb/c

Вывод:
0
1
0
0

Вывод:
4 0
*.bb/c
*.bb/c/*
bb/c/*
bb/c/*
6
bb
bb/c
bb/c/d
a.bb
a.bb/c
a.bb/c/d

Вывод:
0
4
3
0
2
1

ID 21954. Ремонт асфальта

Темы: Структуры данных Задача на реализацию

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

Вы, как коренной житель города Д. и программист по призванию, решили использовать свои профессиональные навыки на благо общества и облегчить жизнь своим соседям по улице М. А именно, вы решили создать сайт, содержащий актуальную информацию о непроходимости улицы. Прежде всего, вы заметили, что улица разбита на N идущих друг за другом участков единичной длины. По странному совпадению бригада рабочих всегда выбирает для ремонта ровно один из таких участков и целиком меняет тип асфальта на нём. Затем вы пронумеровали эти участки от 1 до N и собрали информацию о типе асфальта на каждом из участков — числа t1, t2, . . . , tN (ti — номер типа асфальта на i-м участке, согласно Государственному реестру дорожных покрытий). Наконец, вы определили непроходимость улицы как минимальное количество непрерывных непересекающихся отрезков c одинаковым типом асфальта, на которые она разбивается. Например, непроходимость улицы 110111 равна 3, потому что она состоит из трёх участков 11, 0 и 111, а идеальная улица 2222 имеет непроходимость, равную 1.

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

Формат входных данных
Первая строка входного файла содержит единственное натуральное число N — количество участ- ков дороги (1 <= N <= 100 000). Следующая строка содержит N целых чисел t1, t2, . . . , tN — исходные типы асфальта участков дороги (|ti | <= 109 ). Третья строка содержит единственное натуральное число Q — количество сообщений от жителей об обновлении дорожного покрытия (1 <= Q <= 100 000). Каждая из следующих Q строк содержит очередное сообщение. i-е сообщение представляет собой пару целых чисел pi , ci — номер ремонтируемого участка дороги и новый номер типа асфальта на этом участке (1 <= pi <= N, |ci | <= 109 ). Участки дороги нумеруются от 1 до N в порядке задания их исходного типа асфальта во второй строке входного файла.

Формат выходных данных
Выведите Q строк. i-я строка (1 <= i <= Q) должна содержать единственное целое число — величину непроходимости улицы после первых i обновлений дорожного покрытия.

Примеры

Ввод	Вывод
5 2 2 2 2 2 5 1 2 2 3 4 3 3 1 3 3	1 3 5 5 3
7 1 1 2 3 2 2 1 3 2 2 4 2 6 9	5 3 4

Замечание
Рассмотрим подробнее второй тестовый пример. Изначально улица 1123221 состоит из 5 отрезков с одинаковым типом асфальта: 11, 2, 3, 22, 1 и, соответственно, имеет непроходимость, равную 5 (её не нужно выводить в выходной файл).
После первого ремонта улица станет выглядеть как 1223221 и всё ещё будет состоять из 5 участ- ков, но других: 1, 22, 3, 22, 1. Поэтому её непроходимость равна 5, и первое число в выходном файле равно 5.
После второго ремонта улица будет состоять из 3 участков: 1, 22222, 1, так что второе число в выходном файле — 3.
После третьего ремонта получим 4 участка: 1, 2222, 9, 1, соответственно, третье и последнее число в выходном файле — 4.

ID 21998. Урок физкультуры

Темы: Структуры данных Дерево отрезков, RSQ, RMQ Сканирующая прямая Словари

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

Всего на урок пришло N детей, изначально построившихся таким образом, что рост стоящего на позиции i равен hi (используется нумерация c 1). Можно считать, что все числа hi различны и лежат в диапазоне от 1 до N. Шеренга считается упорядоченной, если на первой позиции стоит школьник ростом один, на второй позиции стоит школьник ростом два и так далее.

Феоктист Всеволодович получает большое удовольствие от процесса упорядочивания школьни- ков, поэтому он всегда выбирает наиболее длинную последовательность обменов. С другой стороны, он не хочет чтобы ученики догадались о том, что он умышленно затягивает построение, поэтому никогда не делает заведомо бессмысленных обменов. А именно, преподаватель никогда не меняет местами школьников на позициях i и j, если hi < h_j . Очевидно, что данное ограничение делает процесс сортировки шеренги по росту конечным.

Староста Саша очень любит играть в волейбол и прекрасно понимает, что чем дольше препо- даватель будет расставлять всех по местам, тем меньше времени останется для игры. Ученики уже построились некоторым образом, а Феоктист Всеволодович вышел поговорить по телефону, так что Саша может успеть поменять местами ровно двух школьников, необязательно стоящих рядом в ше- ренге. Разумеется, он хочет сделать это таким образом, чтобы преподаватель как можно быстрее закончил упорядочивать шеренгу (Саша давно уже раскусил, как именно действует Феоктист Всево- лодович). С информатикой у старосты всегда были определённые проблемы, поэтому ему требуется ваша помощь.

Формат входных данных
В первой строке ввода содержится единственное число N — количество школьников на уроке (1 <= N <= 1 000 000). Во второй строке записано N различных целых чисел h_i (1 <= h_i <= N). i-е число соответствует росту школьника стоящего на i-й позиции.

Формат выходных данных
Выведите два числа — номера позиций школьников, которым необходимо поменяться местами, чтобы минимизировать количество действий преподавателя. Если таких пар несколько, то выведите любую из них. Если никому меняться местами не нужно, выведите -1 -1.

Ввод	Вывод
5 2 4 3 5 1	2 5
4 1 2 3 4	-1 -1
10 2 3 7 1 5 10 4 6 9 8	3 7

ID 21953. Пожар в НИИЧАВО

Темы: Обход в ширину Структуры данных Алгоритмы на графах

В научно-исследовательском институте чародейства и волшебства пожар! Во время опыта Кор- неева В. П. по превращению всей морской и океанской воды планеты в живую воду произошло короткое замыкание, и теперь его кабинет объят пламенем. Задача первостепенной важности — спасти из огня ценные лабораторные приборы, в особенности единственный в своём роде диван- транслятор µ-поля. Ваша задача — перенести диван-транслятор из кабинета Корнеева в запасную лабораторию изучения µ-поля.

НИИЧАВО состоит из N кабинетов, соединённых M коридорами. Кабинеты пронумерованы це- лыми числами от 1 до N, при этом кабинет Корнеева имеет номер A, а лаборатория изучения µ-поля расположена в кабинете номер B. Благодаря специальному искажению пространства внутри инсти- тута, все коридоры имеют одинаковую длину, которую можно пройти за 1 минуту, если двигаться быстрым шагом.

Ситуация усугубляется тем, что диван-транслятор — прибор, очень чувствительный к резким пе- репадам температуры. Внутри каждого коридора НИИЧАВО поддерживается свой температурный режим. Если абсолютная величина разности температур в двух последовательных коридорах на пути из кабинета Корнеева в лабораторию окажется больше D градусов, то диван-транслятор пе- рейдёт в нестабильное состояние, что может привести к катастрофическим последствиям. Обратите внимание, что на своём пути вы не заходите в сами кабинеты, а только переходите из коридора в коридор, поэтому климат внутри кабинетов не влияет на диван-транслятор. В силу причин магиче- ского характера, войдя в коридор, вы обязаны дойти до его конца, иными словами, останавливаться или разворачиваться посреди коридора запрещено. По каждому коридору можно перемещаться в обоих направлениях.

Определите, за какое минимальное время можно добраться из кабинета Корнеева до запасной лаборатории, не допуская резкого перепада температур. В рамках данной задачи вам предлагается ответить на поставленный вопрос для нескольких пар значений A и B.

Формат входных данных
В первой строке входных данных следуют три целых числа N, M и D (2 <= N <= 100 000, 1 <= M <= 200 000, 0 <= D <= 2 · 10⁸ ), обозначающие количество кабинетов, количество коридоров в НИИЧАВО и максимальный допустимый перепад температур для дивана-транслятора в граду- сах. В последующих M строках находятся описания коридоров. Каждая строка содержит по три целых числа ui , vi , ti — номера двух кабинетов, соединённых i-м коридором, и значение температуры в этом коридоре, выраженное в градусах (1 <= ui , vi <= N, −109 <= ti <= 10⁹ ). Как вы уже могли понять, НИИЧАВО — весьма необычное заведение, поэтому между двумя кабинетами может пролегать несколько коридоров, возможно с разными температурами, а некоторые коридоры могут соединять кабинет с самим собой. Гарантируется, что коридоры перечислены во входном файле в порядке неубывания ti . В следующей строке находится целое число Q (1 <= Q <= 50) — количество пар A и B, которые вам требуется обработать. В каждой из последующих Q строк находятся по два целых числа Ai , Bi , обозначающих номер кабинета Корнеева и номер кабинета, в котором расположена лаборатория (1 <= A_i , B_i <= N, A_i != B_i).

Формат выходных данных
Для каждого набора данных выведите в отдельной строке минимальное количество минут, ко- торое требуется потратить, чтобы добраться из кабинета Корнеева до лаборатории, либо выведите −1, если сделать это, используя допустимый для дивана-транслятора маршрут, невозможно.

Примеры

Ввод	Вывод
6 9 5 6 6 -42 1 2 4 2 3 6 3 2 7 2 5 11 6 1 12 1 3 15 3 4 16 5 6 18 2 1 5 4 2	4 -1
6 9 7 6 6 -42 1 2 4 2 3 6 3 2 7 2 5 11 6 1 12 1 3 15 3 4 16 5 6 18 1 4 2	5

Замечание
Пояснение к тестам из условия. В обоих тестах план НИИЧАВО выглядит следующим образом:

Рассмотрим первый тест, в нём D = 5. В первом наборе A = 1, B = 5. В качестве воз- можного маршрута может выступить следующая последовательность переходов по коридорам:

Третьим шагом можно вернуться в кабинет 2 и по тому же коридору с t = 6 .
Во втором наборе A = 4, B = 2. Способа добраться из кабинета 4 в кабинет 2, ни разу не допустив перепад температуры больше, чем в 5 градусов, не существует.

Во втором тесте D = 7. В единственном наборе A = 4, B = 2 cтартовый и конечный кабинет те же, что и во втором наборе первого теста из условия, но допустимый перепад температур больше, благодаря чему подходит следующий маршрут:

ID 27098. Шифрование

Темы: Задача на реализацию Множества Структуры данных

Одним из самых простых способов шифрования открытого текста является шифр простой замены. Он состоит в том, что каждая буква в алфавите, которым написано открытое сообщение, заменяется на какой-то другой символ, например, другую букву того же алфавита. Пусть дана таблица замены, использующая для замены только 33 буквы русского алфавита в верхнем регистре (заглавные буквы):

Сообщение	Шифртекст	Сообщение	Шифртекст	Сообщение	Шифртекст
А	Г	К	Т	Х	З
Б	Ш	Л	Х	Ц	Ж
В	Ы	М	Я	Ч	Л
Г	О	Н	Ь	Ш	Ё
Д	Э	О	Ф	Щ	Н
Е	Ц	П	У	Ъ	Д
Ё	М	Р	К	Ы	Е
Ж	Ъ	С	Ю	Ь	Б
З	Щ	Т	Р	Э	Ч
И	А	У	П	Ю	И
Й	В	Ф	С	Я	Й

Если применить замену, заданную такой таблицей, к слову «ДОМ», получится зашифрованный текст «ЭФЯ». Если применить замену к полученному результату, из «ЭФЯ» получится «ЧСЙ», а из «ЧСЙ» таким способом можно получить текст «ЛЮВ». Известно, что через некоторое количество применений замены полученный результат совпадет с исходным словом «ДОМ», после чего результаты замены начнут повторяться. Определите, сколько различных шифртекстов (включая совпадающий с исходным словом) можно получить из произвольного заданного слова по произвольно заданной таблице замены таким способом.

Рекомендации.
До начала работы над программной реализацией постарайтесь найти ответы на следующие вопросы:
1. Сколько различных зашифрованных текстов (включая и совпадающий с открытым текстом) можно получить одной операцией замены из открытого текста с n различными буквами, используя все возможные таблицы замены.
2.Можно ли получить все возможные зашифрованные тексты (число которых установлено в пункте 1), применяя к результату зашифрования операцию замены символов по одной и той же таблице неограниченное число раз.

Формат ввода:
В первой строке задана строка с алфавитом используемых символов. Во второй строке задана последовательность заглавных букв, заменяющих буквы, стоящие в алфавитном порядке (таблица замены). Например, приведенной выше таблице соответствует строка «ГШЫОЭЦМЪЩАВТХЯЬФУКЮРПСЗЖЛЁНДЕБЧИЙ». В следующей строке задано слово, являющееся открытым текстом – в верхнем регистре (заглавными буквами) без пробелов. Например, слово «КРИПТОАНАЛИЗ».
Каждая из этих строк заканчивается либо символами с кодами 13, 10 (окончание строк DOS – для Pascal ABC .NET), либо символом с кодом 10 (окончание строк Unix) в зависимости от выбранного при сдаче программы типа конца строк. Никаких других символов в двух входных строка не встречается.
Русский текст задан в кодировке Windows-1251 (cp1251). В ней заглавные русские буквы от "А" до "Я" кроме буквы "Ё" имеют коды от 192 (шестнадцатеричное C0) до 223 (шестнадцатеричное DF). Буква "Ё" имеет код 168 (шестнадцатеричное A8). Русские буквы (кроме "Ё") упорядочены по алфавиту.

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

Ввод	Вывод
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ ГШЫОЭЦМЪЩАВТХЯЬФУКЮРПСЗЖЛЁНДЕБЧИЙ КРИПТОАНАЛИЗ	42
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ УКЮРПСЗЖЛЁНДЕБЧИЙГШЫОЭЦМЪЩАВТХЯЬФ СВЕРХСЕКРЕТНО	154

ID 27042. Падающее домино

Темы: Префиксные суммы(минимумы, ...) Структуры данных Разбор случаев

Вася обожает выставлять сложные фигуры из костяшек домино и, толкнув одну из них, смот- реть, как вся конструкция падает. Однако, он сделал уже так много фигур, что решил придумать что-то новое.

Для своей новой идеи он использует костяшки не только длиной 2, но и более длинные (и более короткие). Все костяшки выстраиваются в одну линию на расстоянии 1, а цель игры опрокинуть все костяшки толкнув наименьшее количество костяшек.

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

Формат входных данных

В первой строке записано натуральное число N (0 <= N <= 1 000 000) количество костяшек. Во второй строке записано N натуральных чисел H_i (1 <= Hi <= 1 000 000) высоты костяшек.

Формат выходных данных

Выведите число M наименьшее количество костяшек, которые нужно толкнуть, чтобы вся конструкция упала.

В следующих M строках выведите описание костяшек, которые необходимо толкнуть: номер костяшки (нумерация начинается с единицы и идет слева-направо), а также направление толчка: букву L для толчка влево и R для толчка вправо. Номер костяшки и букву разделяйте пробелом.

Порядок вывода костяшек, которые нужно толкнуть, может быть произвольным. Если решений несколько выведите любое из них

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

Решения, верно работающие при N <= 1000, будут набирать не менее половины баллов.

Ввод	Вывод
6 1 2 1 4 1 3	1 6 L
7 1 2 4 1 2 3 2	2 3 R 2 L

Замечание

В первом примере последняя костяшка толкается влево, опрокидывая костяшки с номерами 4 и 5 (их высоты 4 и 1 соответственно). Костяшка номер 4 также падает налево и опрокидывает костяшки с номерами 1, 2 и 3.

Во втором примере костяшка номер 3 толкается вправо, опрокидывая костяшки номер 4, 5 и 6.

Костяшка номер 6 также падает вправо и опрокидывает костяшку номер 7. После этого костяшка

номер 2 толкается влево и опрокидывает костяшку номер 1.

ID 24765. Воздушные потоки

Темы: Деревья Наименьший общий предок Разреженные таблицы (sparse table) Структуры данных Префиксные суммы(минимумы, ...)

Колобок ушёл от бабушки и поехал путешествовать. Неожиданно для себя он забрёл в страну Ивэнлэнд. Первые трудности встали на его пути: Колобка и вход в страну отделял огромный ров с водой, которая, как известно, не очень хорошо влияет на нашего героя. К счастью, повсюду рас- положены воздушные потоки, которые могли поднимать того, кто на них встает, на определённую высоту. Страна не просто так названа Ивэнлэнд, поэтому все высоты, на которые могут поднять героя воздушные потоки — это чётные числа.

Представим воздушные потоки как массив h[1..n] из n натуральных чисел — высот потоков. Для каждого 1 ≤ i ≤ n посчитаем G[i] — индекс ближайшего элемента слева, строго большего h[i]. Более формально, g[i] = max{j | j < i и h[j] > h[i]}. Если i = 1 или до h[i] нет ни одного элемента больше него, то G[i] считается равным 0.

Колобок считает, что оптимальность расположения воздушных потоков определяется суммой

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

Помогите Колобку сделать оптимальное изменение, которое позволит добиться, чтобы сумма S(h), описанная выше, после проделанного действия была минимальна.

Формат входного файла
В первой строке входного файла даны числа n, m (1 ≤ n ≤ 10⁵ , 1 ≤ m ≤ 10⁹ ) — количество воздушных потоков и максимальное значение, на которое можно увеличить высоту одного из них. Во второй строке даны высоты воздушных потоков h[i] (1 ≤ h[i] ≤ 10⁹ ). Гарантируется, что все высоты — чётные числа.

Формат выходного файла
В единственной строке выходного файла выведите одно целое число — минимальную искомую сумму.

Ввод	Вывод
3 100 4 2 6	4
3 2 4 2 6	5
3 10 2 2 2	4

ID 24763. Карандаши

Темы: Структуры данных

Новое увлечение Колобка — рисование. Он решил купить k наборов карандашей. Каждый набор состоит из одного или нескольких карандашей. Каждый карандаш имеет положительную длину, которая выражается целым числом миллиметров.

В магазине продаются n наборов карандашей. После того, как Колобок купит ровно k наборов, он придёт домой и сложит все карандаши в одну коробку. Колобок очень обрадуется, если разница в длине между наибольшим и наименьшим карандашами в этой коробке будет минимальна.

Поэтому он просит вас помочь ему: выберите из n наборов карандашей ровно k так, чтобы разница между максимальным и минимальным среди всех купленных карандашей была как можно меньше.

Формат входного файла
В первой строке находятся два натуральных числа n, k (1 ≤ n ≤ 10⁵ , 1 ≤ k ≤ n) — количество наборов карандашей, имеющихся в магазине, и количество наборов, необходимое Колобку. В каждой из следующих n строк находится ci (1 ≤ ci ≤ 2·10⁵ ) — количество карандашей в наборе. Далее, в этой же строке, следуют ci натуральных чисел aij (1 ≤ a_ij ≤ 10⁹ ) — длины карандашей в i-м наборе. Гарантируется, что сумма всех c_i не превосходит 2 · 10⁵ .

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

Ввод	Вывод
3 2 3 1 3 4 3 5 1 2 1 4	3
5 3 3 2 1 3 2 4 1 3 4 2 4 4 3 2 3 3 2 5 6	3

ID 24761. Путь в никуда

Темы: Деревья Деревья Структуры данных Разреженные таблицы (sparse table) Бинарный поиск Префиксные суммы(минимумы, ...)

Колобку снится странный сон.
В нём Колобок находится на клетчатом поле размера n × m в клетке с координатами (x, y).
Изначально Колобок смотрит вдоль положительного направления оси X. Затем он начинает идти по полю со следующей закономерностью:
• Пройти на одну клетку вперед. Повернуть на 90^oвправо.
• Пройти на одну клетку вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на четыре клетки вперед. Повернуть на 90^o вправо.
• И так далее...

Движение продолжается до тех пор, пока Колобок не выйдет за границы поля. После этого Колобок просыпается.

Утром Колобок решил проанализировать свой сон. Он догадался, что в каждой клетке он был максимум один раз, но никак не может вспомнить, сколько клеток он посетил. Колобок просит вас написать программу, которая посчитает количество посещённых им клеток.

Формат входного файла
В первой строке входного файла находятся два натуральных числа n, m (1 ≤ n, m ≤ 10⁹ ) — размеры доски вдоль оси X и оси Y соответственно. Во второй строке находятся два натуральных числа x, y (1 ≤ x ≤ n; 1 ≤ y ≤ m) — координаты стартовой позиции колобка.

Формат выходного файла
В выходной файл выведите одно число — количество клеток, посещенных Колобком во сне.

Вывод	Ввод
7 6 3 4	36
2 2 1 1	2
2 2 1 2	4

Комментарий
На рисунке наглядно показан первый пример.

ID 27216. Switch Grass

Темы: Минимальный каркас Структуры данных Дерево отрезков, RSQ, RMQ Обход в глубину Алгоритмы на графах

Фермер Джон обнаружил, что разные типы коров любят разные типы травы. Однако он должен правильно их высаживать, чтобы не навредить.

Ферма Джона состоит из NN (1≤N≤200,000), полей, и MM пар полей соединены двунаправленными дорожками (1≤M≤200,000). Используя эти дорожки, можно пройти от любого поля к любому другому полю. Каждая дорожка имеет целочисленную длину в интервале 1…1,000,000. Любая пара полей соединена не более чем одной прямой дорожкой.

В каждом поле ФД изначально посадил один из KK типов травы (1≤K≤N). Через некоторое время, однако, он может решить изменить тип травы на некоторых из полей. Он называет это операцией "обновления".

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

В 30 процентах тестов каждое поле непосредственно соединено не более чем с 10 дорожками.

ФОРМАТ ВВОДА:

Первая строка ввода содержит четыре целых числа N, M, K, Q, где Q - количество операций обновления (1≤Q≤200,000). Следующие M строк описывают дорожки. Каждая строка содержит три целых числа A, B, L, указывающих, что есть дорожка между полями A, B и её длина L. (A, B - целые числа в интервале 1…N). Следующая строка указывает начальный тип травы для каждого поля (N целых чисел в интервале 1…K). Затем идут Q строк, каждая из которых описывает одну операцию обновления двумя целыми числами A и B, означающими, что на поле A типе травы изменён на B.

ФОРМАТ ВЫВОДА:

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

Ввод	Вывод
3 2 3 4 1 2 3 2 3 1 1 1 2 3 3 2 3 1 2 2 2	1 3 3 1

ID 27295. Trapped in the Haybales

Темы: Динамическое программирование: один параметр Динамическое программирование Дерево отрезков, RSQ, RMQ Структуры данных

Фермер Джон получили груз из N больших стогов сена (1≤N≤100,000), и разметил их в различных положениях вдоль дороги, ведущей к амбару. К несчастью, он полностью забыл, что корова Беси пасётся вдоль дороги и может попасть в ловушку между стогами сена.

Каждый стог j имеет размер S_j и позицию Pj определяющую его положение вдоль дороги. Беси может двигаться вдоль дороги вплоть до позиции стога, но не может пересечь эту позицию. Исключение – если она прошла в этом направлении D единиц расстояния, тогда она набрала достаточно скорости, чтобы протаранить стог любого размера строго меньше чем D. Конечно после этого она может продолжить движение и таранить другие стога.

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

ФОРМАТ ВООДА:

Первая строка ввода содержит N. Каждая из последующих N строк описывает стог, и содержит два целых числа определяющих размер и позицию в диапазоне 1…10⁹. Все позиции различны.

ФОРМАТ ВЫВОДА:

Выведите одно целое число – размер области дороги, откуда Беси не сможет выбраться.

Ввод	Вывод
5 8 1 1 4 8 8 7 15 4 20	14

ID 27298. Censoring

Темы: Строки Хеш Структуры данных

Фермер Джон купил подписку журнала Good Hooveskeeping для своих коров. К сожалению, последний номер содержит неподходящую статью - как приготовить бифштекс. ФД не хочет, чтобы его коровы её читали.

ФД взял текст журнала, создал строку S длиной не более чем 10^5 символов. У него есть список слов t_1, t_2, ..., t_N, которые он хочет удалить из S. Поэтому ФД находит ближайшее вхождение слова из списка T (то есь с наименьшим индексом) и удаляет его из S. Затем он продолжает это процесс опять, пока в S не останется слов из T. Заметим, что удаление слова может создавать новое вхождение свлоа из T, которое не существовало ранее.

ФД заметил, что слова из списка T обладают таким свойством, что никакое из них не является подстрокой другого слова из T. В частности, это означает, что ранее вхождение слова из T в S всегда определено однозначно. Пожалуйста, помогите ФД определить финальное содержание строки S.

INPUT FORMAT:

Первая строка содержит S. Вторая строка содержит N - количество удаляемых слов. Последующие N строк содержат строки t_1, t_2, ..., t_N. Каждая строка содержит только маленькие латинские буквы (a..z) и суммарная длина всех строк не превысит 10^5.

OUTPUT FORMAT:

Строка S после всех удалений. Гарантируется, что S не станет пустой.

Ввод	Вывод
begintheescapexecutionatthebreakofdawn 2 escape execution	beginthatthebreakofdawn

ID 27300. Cow Curling

Темы: Вычислительная геометрия Динамическое программирование Структуры данных

В коровий кёрлинг вовлечены две команды, каждая из которых двигает N тяжёлых камней (3 <= N <= 50,000) по льду. В конце игры имеется 2N камней на льду, каждый из которых расположен в различной точке

плоскости.

Подсчёт очков в коровьем кёрлинге ведётся следующим образом:

Камень считается «захваченным», если он содержится внутри треугольника, по углам которого находятся камни противника (камень, который находится на границе такого треугольника, также считается захваченным). Счёт команды есть количество камней команды противника, которые «захвачены».

Вычислите финальный счёт матча по коровьему кёрлингу, по заданному расположению всех камней.

INPUT FORMAT:

* Строка 1: Целое число N.

* Строки 2..1+N: Каждая строка содержит 2 целых числа, указывающих x и y координаты камня команды A (каждая координата лежит в диапазоне -40,000 .. +40,000).

* Строки 2+N..1+2N: Каждая строка содержит 2 целых числа, указывающих x и y координаты камня команды B (каждая координата лежит в диапазоне -40,000 .. +40,000).

OUTPUT FORMAT:

* Строка 1: Два разделённых пробелом целых числа, представляющих счета команд A и B

SAMPLE:

Ввод	Вывод
4 0 0 0 2 2 0 2 2 1 1 1 10 -10 3 10 3	1 2

INPUT DETAILS:

У каждой команды по 4 камня.

Команда A имеет камни (0,0), (0,2), (2,0), (2,2).

Команда B имеет камни (1,1), (1,10), (-10,3), (10,3).

OUTPUT DETAILS:

Команда A захватила камень противника в точке (1,1).

Команда B захватила камни противника в точках (0,2) и (2,2).

ID 29545. Load Balancing

Темы: Дерево Фенвика Дерево отрезков, RSQ, RMQ Структуры данных Тернарный поиск

Коровы Фермера Джона стоят в различных точках (x₁,y₁)…(x_n,y_n) его поля (1≤N≤100,000, все x_i и y_i - положительные нечётные целые числа, не превышающие 1,000,000. ФД хочет разделить своё поле изгородью бесконечной длины с севера на юг, описываемой уравнением x=a (a - чётное целое, так обеспечивается, что изгородь не пройдёт через позицию ни одной коровы). Также он хочет построить изгородь бесконечной длины с востока на запад, которая описывается уравнением y=b, где b - чётное целое. Эти две изгороди пересекаются в точке (a,b), и вместе делят поле на четыре региона.

ФД хочет выбрать a и b так, чтобы получить "сбалансированное" количество коров во всех регионах, т.е. чтобы не было региона, который содержит слишком много коров. Пусть M - максимальное количество коров в этих четырёх регионах, ФД хочет, чтобы M было как можно меньше. Помогите ФД определить это минимально возможное значение для M.

ФОРМАТ ВВОДА:

Первая строка ввода содержит одно целое число, N. Каждая из следующих n строк содержит местоположение одной коровы, указанное её координатами x и y.

ФОРМАТ ВЫВОДА:

Выведите минимально возможное значение M, которое может достичь ФД оптимальным расположением изгородей.

Ввод	Вывод
7 7 3 5 5 7 13 3 1 11 7 5 3 9 1	2

ID 44511. Башни 3.0

Темы: Структуры данных Дерево отрезков, RSQ, RMQ Дерево отрезков, RSQ, RMQ

В компьютерной игре есть n башен, высота i-й башни равна a_i метров. Определим расстояние между двумя башнями с индексами i и j как |i−j|. Разрешается прыгнуть с i-й башни на j-ю башню тогда и только тогда, когда не существует такого индекса 1 <= k <= n, такого, что расстояние от i-й до j-й башни не меньше расстояния от i-й башни до k-й башни, и k-я башня имеет большую высоту, чем j-я. Башня j достижима из башни i если существует последовательность корректных прыжков, которая начинается в i-й башне и заканчивается в j-й.

Вам даны q запросов вида (u,v,l,r). Для каждого запроса посчитайте количество индексов l <= k <= r, таких, что k-я башня достижима из u-й башни и из v-й башни. Обратите внимание, что во многих подзадачах выполняется ограничение u=v, l=1, r=n, то есть ответом на запрос будет общее число башен, достижимых из u .

Входные данные
Первая строка входных данных содержит одно целое число n (1 <= n <= 500000) - количество башен.
Вторая строка входных данных содержит n чисел a₁, a₂, ..., a_n (1 <= a_n<= 10⁹) - высоты башен.

Третья строка входных данных содержит одно целое число q (1 <= q <= 500000) - количество запросов.

Следующие q строк описывают запросы. i-я из них описывает i-й запрос и содержит четыре целых числа u_i, v_i, l_i, r_i (1<= u_i, v_i <= n, 1 <= l_i <= r_i <= n) - индексы вершин запроса и границы отрезка запроса.

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

Выведите n чисел, i-е из которых должно быть равным ответу на i-й запрос.

Примечание

В первых двух примерах запросы спрашивают количество достижимых из каждой башни башен.

В первом примере с 1-й башни можно прыгнуть на башни 1 и 5. Любая другая башня имеет меньшую высоту, чем башня 1, поэтому туда нельзя прыгнуть (в качестве k можно выбрать 1). Множество достижимых из 1-й башни также состоит из башен 1 и 5. Со второй башни можно прыгнуть на башни 1, 2, и 5, они же являются множеством достижимых. С третьей башни можно прыгнуть на башни 2, 3, 5. Однако, башня 1 также является достижимой, поскольку можно сделать два прыжка: 3→2→1. Таким образом, получается 4 достижимые башни. С 4-й башни можно прыгнуть на башни 4 и 5, они же являются единственными достижимыми. Из 5-й башни достижима только она сама.

Во втором примере из 1-й и из 2-й башни достижимы башни 1,2,3,4,5. Из 3-й башни достижимы башни 3,4,5. Из 4-й и 5-й башни достижимы башни 4,5. Из 6-й башни достижимы башни 4,5,6. Из 7-й башни достижимы башни 4,5,6,7.

Рассмотрим третий пример:

В первом запросе множество индексов башен k на отрезке [l,r], достижимых из u и из v — {3,6}.
Во втором запросе множество индексов башен k на отрезке [l,r], достижимых из u и из v — {6}.
В третьем запросе множество индексов башен k на отрезке [l,r], достижимых из u и из v — {3}.
В четвёртом запросе множество индексов башен k на отрезке [l,r], достижимых из u и из v пусто.
В пятом запросе множество индексов башен k на отрезке [l,r], достижимых из u и из v — {6}.

Примеры

№

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

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

7
1 1 1 2 2 1 1
7
1 1 1 7
2 2 1 7
3 3 1 7
4 4 1 7
5 5 1 7
6 6 1 7
7 7 1 7

7
6 8 9 3 5 10 1
5
1 3 2 7
4 5 1 6
1 4 2 4
4 7 1 3
1 5 3 6

ID 44509. Башни 2.0

Темы: Задача на реализацию Структуры данных Структуры данных Алгоритмы обработки Линейные алгоритмы Алгоритмы обработки

Первая строка входных данных содержит одно целое число n (1 <= n <= 500000) - количество башен.

Вторая строка входных данных содержит n чисел a₁, a₂, ..., a_n (1 <= a_n<= 10⁹) - высоты башен.

Выходные данные
Выведите n чисел, i-е из которых должно быть равным количеству башен, достижимых из i-й башни.

Примечание

В первом примере с 1-й башни можно прыгнуть на башни 1 и 5. Любая другая башня имеет меньшую высоту, чем башня 1, поэтому туда нельзя прыгнуть (в качестве k можно выбрать 1). Множество достижимых из 1-й башни также состоит из башен 1 и 5. Со второй башни можно прыгнуть на башни 1, 2, и 5, они же являются множеством достижимых. С третьей башни можно прыгнуть на башни 2, 3, 5. Однако, башня 1 также является достижимой, поскольку можно сделать два прыжка: 3→2→1. Таким образом, получается 4 достижимые башни. С 4-й башни можно прыгнуть на башни 4 и 5, они же являются единственными достижимыми. Из 5-й башни достижима только она сама.

Примеры

№	Входные данные	Выходные данные
1	5 7 6 3 4 10	2 3 4 2 1
2	7 1 1 1 2 2 1 1	5 5 3 2 2 3 4

ID 33123. Лифт

Темы: Задача на реализацию Сортировка событий Использование сортировки Множества Структуры данных

В современном многоэтажном офисе крупной компании установлен новый лифт. В

компании работает n сотрудников. Для проверки эффективности системы управления

лифтом требуется провести моделирование его работы в конце рабочего дня, когда все

сотрудники должны покинуть здание и спуститься на первый этаж.

В здании m этажей, пронумерованных от 1 до m снизу-вверх. Известно, что i-й

сотрудник подходит к лифту в секунду ti на этаже ai, чтобы спуститься на первый этаж.

На каждом этаже могут находиться люди, ожидающие лифт. Когда очередной

сотрудник подходит к лифту, он вызывает лифт, если на этом этаже лифт еще не вызван,

либо присоединяется к ожидающим лифт. Таким образом, помимо вызвавшего лифт, вместе

с ним лифт могут ожидать и другие сотрудники.

В каждый момент времени не более одного вызова является активным.

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

вызов, этот вызов становится активным и лифт отправляется на соответствующий этаж. Если

несколько вызовов поступает одновременно, активным становится вызов от сотрудника с

меньшим номером.

Лифт перемещается между этажами со скоростью один этаж в секунду. Когда лифт

оказывается на этаже, откуда был сделан активный вызов, в него заходят все, кто уже

ожидает лифт на этом этаже, и лифт отправляется вниз на первый этаж, со скоростью один

этаж в секунду.

При движении вниз лифт останавливается на тех этажах, в которых был сделан вызов

на момент проезда лифта мимо этого этажа. Все ожидающие лифт сотрудники заходят в него

и вызов на этом этаже сбрасывается. Когда лифт завершает движение на первом этаже, все

люди выходят из лифта, а лифт ожидает следующего вызова.

Если в момент, когда лифт освободился, есть хотя бы один необслуженный вызов,

активируется вызов, который поступил раньше других. Если несколько вызовов поступило

одновременно, активируется вызов от сотрудника с меньшим номером. Лифт продолжает

обслуживание описанным образом, пока все n сотрудников не окажутся на первом этаже.

Будем считать, что люди входят и выходят из лифта мгновенно. Каждую секунду

сначала люди подходят и вызывают лифт, а затем выполняются соответствующие действия

(лифт перемещается на соседний этаж, в него входят или из него выходят люди, принимается

решение, на какой вызов лифт должен отреагировать).

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

сотрудника определяет, в какой момент этот сотрудник окажется на первом этаже.

Формат входных данных

Первая строка входных данных содержит целые числа n и m — количество людей,

вызывающих лифт, и количество этажей в здании (1 ≤ n ≤ 10⁵, 2 ≤ m ≤ 10⁹).

Следующие n строк описывают сотрудников, i-я из этих строк содержит два целых

числа ti и ai — секунду, в которую i-й сотрудник подходит к лифту, и номер этажа, на

котором это происходит (1 ≤ t1 ≤ t2 ≤ … ≤ tn ≤ 10⁹, 2 ≤ ai ≤ m)

Формат выходных данных

Выходные данные должны содержать n целых чисел, для каждого сотрудника

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

Ввод	Вывод
5 4 2 3 2 4 5 2 5 3 9 3	6 12 6 12 12

Пояснение к примеру

Пример работы лифта по шагам показан в следующей таблице.

Использованные в пояснении к примеру обозначения

ID 33128. Обработка больших данных

Темы: Структуры данных Множества Динамическое программирование

В научной лаборатории разрабатывается новая архитектура суперкомпьютера,

позволяющая эффективно обрабатывать большие объемы данных.

Суперкомпьютер имеет 2^k ячеек памяти, пронумерованных от 0 до 2^{k– 1}. Отрезком

[L, R] называется последовательность подряд идущих ячеек памяти с номерами от L до R,

включительно.

Некоторые отрезки памяти являются корректными. Отрезок памяти [L, R] является

корректным, если его длина (R – L + 1) равна 2i для некоторого i, а число L делится на 2i.

Например, если k = 3, то ячейки памяти пронумерованы от 0 до 7, а корректными являются

отрезки [0, 7], [0, 3], [4, 7], [0, 1], [2, 3], [4, 5], [6, 7], [0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6,

6] и [7, 7].

Ключевой операцией в новой архитектуре является операция STORE, которая за одно

действие присваивает одно и то же значение всем ячейкам памяти некоторого корректного

отрезка.

Исходно все ячейки памяти содержат значение 0. В лаборатории планируют запустить

на суперкомпьютере программу обработки данных, но перед её запуском необходимо

инициализировать память определенным образом. А именно: первые с1 ячеек памяти

необходимо заполнить значениями v1, следующие c2 ячеек — значениями v2, и так далее,

последние cn ячеек памяти необходимо заполнить значениями vn, где 1 ≤ vi ≤ m.

Ученым надо выяснить, какое минимальное количество операций STORE необходимо

выполнить, чтобы проинициализировать память требуемым образом.

Например, если k = 3, n = 3, m = 2, c1 = 1, v1 = 1, c2 = 2, v2 = 2, c3 = 5, v3 = 1, то итоговое

содержимое памяти должно быть следующим: [1, 2, 2, 1, 1, 1, 1, 1]. В этом случае для

инициализации памяти достаточно трех операций STORE:

- STORE([0, 7], 1), после этой операции все ячейки памяти содержат значение 1;

- STORE([1, 1], 2), после этой операции содержимое памяти [1, 2, 1, 1, 1, 1, 1, 1];

- STORE([2, 2], 2) , после этой операции содержимое памяти [1, 2, 2, 1, 1, 1, 1, 1],

как и требуется.

Заметим, что операцию STORE([1, 2], 2) выполнить нельзя, потому что [1, 2] не

является корректным отрезком памяти.

Требуется написать программу, которая по заданному содержимому памяти

определяет минимальное количество операций STORE, которое необходимо выполнить для

инициализации памяти заданным образом.

Формат входных данных

Первая строка входных данных содержит три целых числа: k, n и m (0 ≤ k ≤ 30,1 ≤ n ≤ 10

5, 1 ≤ m ≤ 10⁹).

Следующие n строк содержат по два целых числа, i-я из этих строк содержит числа ci

и vi (1 ≤ ci ≤ 2^k, 1 ≤ vi ≤ m, c1 + c2 + … + cn = 2^k).

Формат выходных данных

Требуется вывести одно целое число – минимальное количество операций STORE,

которое необходимо выполнить для инициализации памяти заданным образом.

Ввод	Вывод
3 3 2 1 1 2 2 5 1	3

ID 34778. Турнир

Темы: Задачи на моделирование Задача на реализацию Структуры данных

В турнире участвуют N команд. Турнир проводится по олимпийской системе (команды играют на вылет, проигравшие команды выбывают из турнира, выигравшие проходят в следующий тур, ничьих не бывает). Число команд в этой задаче будет степенью двойки: N = 2 ^k .

Все команды пронумерованы числами от 1 до N. В первом туре играют команды с номерами 1 и 2, 3 и 4, 5 и 6 и т. д., всего играется N/2 матчей. По результатам этих матчей команды выходят во второй тур. Во втором туре играют победители первой и второй игры первого тура, победители третьей и четвёртой игры первого тура и т. д. Они выходят в третий тур. В третьем туре играют вместе победители первой и второй игры второго тура, победители третьей и четвёртой игры второго тура и т. д.

Вам даны результаты всех матчей. Определите номер команды, которая стала победителем турнира.
В первой строке входных данных записано число N – количество команд, участвовавших в турнире. Оно является степенью двойки и может принимать значения от 2⁰ = 1 до 2¹⁶ = 65536. Следующие N − 1 строк содержат результаты всех сыгранных матчей. Первые N/2 строк из них являются результатами матчей первого тура, затем идёт N/4 строк с результатами второго тура, N/8 строк с результатами третьего тура и т. д.

Результат каждого матча является одним из двух возможных чисел: 1 или 2. Число 1 означает, что в матче выиграла первая команда (номер которой меньше), число 2 означает, что в матче выиграла вторая команда (номер которой больше).
Программа должна вывести одно число – номер победившей в турнире команды.

Ввод	Вывод
8 1 2 2 1 2 1 1	4

Примечание к ответу
Далее нарисована схема турнира для примера из условия. В турнире участвовало 8 команд. Результаты матчей: 1, 2, 2, 1, 2, 1, 1.
В первом туре играли команды 1 и 2, 3 и 4, 5 и 6, 7 и 8. Результаты матчей первого тура: 1, 2, 2, 1, во второй тур вышли команды 1, 4, 6, 7.
Во втором туре играли команды 1 и 4, 6 и 7. Результаты матчей второго тура: 2, 1.
В третий тур вышли команды 4 и 6. В последнем, третьем, туре играют команды 4 и 6, результат матча: 1, поэтому победителем турнира является команда 4.

ID 50981. Даша и поиски

Темы: Конструктив Структуры данных

Как вы знаете, девочка Даша постоянно что-то ищет. На этот раз ей дали перестановку, и она хочет найти такой её подотрезок, что ни один из элементов на его концах не является ни минимумом, ни максимумом всего подотрезка. Более формально, вас просят найти такие числа \(l\) и \(r\) \((1 \leqslant l \leqslant r \leqslant n)\), что \(a_l \neq \min(a_l, a_{l + 1}, \ldots, a_r)\), \(a_l \neq \max(a_l, a_{l + 1}, \ldots, a_r)\) и \(a_r \neq \min(a_l, a_{l + 1}, \ldots, a_r)\), \(a_r \neq \max(a_l, a_{l + 1}, \ldots, a_r)\).

Напомнима, что перестановкой длины \(n\) называется массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\), выписанных в произвольном порядке. Например, \([2,3,1,5,4]\) является перестановкой, но \([1,2,2]\) не является перестановкой (\(2\) встречается дважды в массиве) и \([1,3,4]\) тоже не является перестановкой (\(n=3\), но \(4\) присутствует в массиве, а \(2\) отсутствует).

Помогите Даше найти такой подотрезок, либо скажите, что такого подотрезка не существует.

Формат входных данных
В первой строке входных данных вам дано одно целое число \(n\) (\(1 \leqslant n \leqslant 200\,000\)) — размер перестановки.

Во второй строке входных данных вам дано \(n\) целых чисел \(a_1, a_2, \ldots a_n\) (\(1 \leqslant a_i \leqslant n\)) — элементы перестановки.

Формат выходных данных
Если искомого подотрезка не существует, выведите \(-1\).

Иначе выведите такие два числа \(l\) и \(r\) \((1 \leqslant l \leqslant r \leqslant n)\), что \([a_l, a_{l + 1}, \ldots, a_r]\) удовлетворяет условиям задачи.

Если искомых подотрезков несколько, выведите любой из них.

ID 60228. Суммы модулей

Темы: Комбинаторика Вывод формулы Структуры данных

Для последовательности целых чисел \(a_1, a_2, \ldots, a_n\) и целого числа \(x\) обозначим через \(f(a, x)\) количество таких целых \(i\) от \(1\) до \(n\), что \(a_i \le x\).

Для пары последовательностей целых чисел \(a_1, a_2, \ldots, a_n\) и \(b_1, b_2, \ldots, b_n\) обозначим через \(g(a, b, c)\) сумму значений \(|f(a, x)-f(b, x)|\) по всем целым \(x\), лежащим в отрезке \([0, c]\). Более формально, \(g(a, b, c) = \sum_{x=0}^c |f(a, x)-f(b, x)|\).

Вам даны два целых числа \(n\) и \(c\), а также две последовательности целых чисел \(a_1, a_2, \ldots, a_n\) и \(b_1, b_2, \ldots, b_n\), все элементы которых лежат в отрезке \([-1, c]\). Известно, что ни в \(a\), ни в \(b\) нет двух подряд идущих элементов, равных \(-1\).

Скажем, что пара последовательностей целых чисел \(a_1', a_2', \ldots, a_n'\) и \(b_1', b_2', \ldots, b_n'\), все элементы которых лежат в отрезке \([0, c]\), соответствует шаблону \((a, b)\), если выполняются следующие условия:

Для всех \(i\) (\(1 \le i \le n\)), таких, что \(a_i \ne -1\), выполняется \(a_i'=a_i\).
Для всех \(i\) (\(1 \le i \le n\)), таких, что \(b_i \ne -1\), выполняется \(b_i'=b_i\).
Для всех \(i\) (\(1 \le i \le n-1\)) выполняется \(a_i' \le a_{i+1}'\).
Для всех \(i\) (\(1 \le i \le n-1\)) выполняется \(b_i' \le b_{i+1}'\).

Обозначим через \(h(a, b, c)\) сумму значений \(g(a', b', c)\) по всем парам последовательностей \((a', b')\), соответствующих шаблону \((a, b)\). Вы должны посчитать \(h(a, b, c)\). Также вы должны обработать \(q\) запросов изменения последовательностей \(a\) и \(b\) и посчитать \(h(a, b, c)\) после каждого изменения. Обратите внимание, что ни в \(a\), ни в \(b\) нет двух подряд идущих элементов, равных \(-1\), ни до всех запросов, ни после какого-либо запроса.

Формат входных данных
Первая строка содержит три целых числа \(n\), \(c\) и \(q\) (\(1 \le n \le 100\,000\), \(0 \le c \le 10^9\), \(0 \le q \le 100\,000\)) — длина последовательностей \(a\) и \(b\), ограничение на значения элементов \(a\) и \(b\) и количество запросов, соответственно.

Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(-1 \le a_i \le c\)) — последовательность \(a\).

Третья строка содержит \(n\) целых чисел \(b_1, b_2, \ldots, b_n\) (\(-1 \le b_i \le c\)) — последовательность \(b\).

В следующих \(q\) строках заданы запросы изменения. Каждый запрос задается тройкой целых чисел \(t\), \(p\), \(x\) (\(1 \le t \le 2\), \(1 \le p \le n\), \(-1 \le x \le c\)). Если \(t=1\), то данный запрос меняет \(a_p\) на \(x\). Если \(t=2\), то данный запрос меняет \(b_p\) на \(x\).

Гарантируется, что до всех изменений и после каждого изменения ни в \(a\), ни в \(b\) нет двух подряд идущих элементов, равных \(-1\).

Формат выходных данных
Выведите \((q+1)\) строку. В \((i+1)\)-й строке (\(0 \le i \le q\)) выведите одно целое число — значение \(h(a, b, c)\) по модулю \(10^9+7\) после применения первых \(i\) запросов изменения.

Примечание
Рассмотрим первый тест из примера. В нем \(n=3\), \(c=4\), \(q=3\). До всех запросов \(a=[-1, 1, 3]\), \(b=[1, -1, 2]\). Шаблону \((a, b)\) соответствуют следующие пары последовательностей:

\(a'=[0, 1, 3], b'=[1, 1, 2]\), \(g(a, b, 4)=2\).
\(a'=[0, 1, 3], b'=[1, 2, 2]\), \(g(a, b, 4)=3\).
\(a'=[1, 1, 3], b'=[1, 1, 2]\), \(g(a, b, 4)=1\).
\(a'=[1, 1, 3], b'=[1, 2, 2]\), \(g(a, b, 4)=2\).

Таким образом, ответ на задачу до всех запросов равен \(h(a, b, 4)=2+3+1+2=8\).

В первом запросе \(t=1\), \(p=1\), \(x=2\). Этот запрос меняет \(a_1\) с \(-1\) на \(2\). Таким образом, после этого запроса \(a=[2, 1, 3]\), \(b=[1, -1, 2]\). В последовательности \(a\) нет \(-1\), поэтому в любой паре последовательностей \((a', b')\), соответствующей шаблону \((a, b)\), последовательность \(a'\) должна совпадать с \(a\). В последовательности \(a\) не выполняется условие \(a_1 \le a_2\), поэтому не существует ни одной пары последовательностей, соответствующей шаблону, а тогда \(h(a, b, 4)=0\) после первого запроса.