Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Контроль доступа#55448

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

Каждый IP-адрес − это 4-байтный номер, который записан байт за байтом в десятичной записи. Байты разделены точками следующим образом: <<byte0.byte1.byte2.byte3>> (кавычки добавлены для ясности). Каждый байт записывается как десятичное число от 0 до 255 (включительно) без ведущих нулей. IP-адреса организованы в IP-сети. IP сети описывается двумя 4-байтовыми числами - сетевым адресом и маской сети. И сетевой адрес и маска сети записаны в той же форме, что и IP-адреса. Для того чтобы понять смысл сетевого адреса и маски сети рассмотрим их двоичное представление. Двоичное представление IP адреса, сетевого адреса и маски сети состоит из 32 бит: 8 бит для byte0 (от старших к младшим), затем по 8 бит для byte1, 8 бит для byte2 и 8 бит для byte3.

IP сеть содержит 2N IP-адресов, где 0≤N≤32. В маске сети первые 32–N бита установлены в единицы, и последние N бит установлены в ноль. Сетевой адрес имеет произвольные 32–N первых бит, а последние N бит установлен в ноль. IP сеть содержит все IP-адреса, первые 32−N бит которых равны 32–N
первых бит сетевого адреса с произвольными N последними битами. Например, IP сеть с сетевым адресом 194.85.160.176 и сетевая маска 255.255.255.248 содержит 8 IP-адресов, с 194.85.160.176 по 194.85.160.183 (включительно).

IP сети, как правило, обозначается как <<byte0.byte1.byte2.byte3/S>>, где <<byte0.byte1.byte2.byte3>> − сетевой адрес, S − это число бит, установленных в единицу в маске сети. Например, IP сети из предыдущего абзаца обозначается как 194.85.160.176/29. Список контроля доступа содержит упорядоченный список правил. Каждое правило имеет одну из следующих форм:

deny from <IP network> − запрещает доступ к ресурсу для любого IP из заданной сети.

deny from <IP address> − запрещает доступ к ресурсу для указанного IP-адреса.

allow from <IP network> − разрешает доступ к ресурсу для любого IP из заданной сети.

allow from <IP address> − разрешает доступ к ресурсу для указанного IP-адреса.

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

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

Входные данные
Первая строка ввода содержит число N − количество правил в списке контроля доступа (0≤N≤100000). Следующие N строк содержат правила по одному в строке. IP сеть всегда записывается как <<byte0.byte1.byte2.byte3/S>>. Следующая строка содержит число M − количество IP адресов, которые следует проверить (0≤M≤100000). Следующие M строк содержат по одному IP адресу в строке.

Выходные данные
Для каждого из M IP-адресов выведите <<A>>, если доступ будет предоставлен, и <<D>> иначе. Все символы следует выводить слитно, не разделяя пробелами.

Бор Дерево отрезков, RSQ, RMQ

✓ 1✗ 0—Войти и решать

Хипуй!#55217

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

a) Insert(k) – добавить в Heap число k (1 ≤ k ≤ 1000000) ;
b) Extract достать из Heap наибольшее число (удалив его при этом).

Входные данные
В первой строке содержится количество команд N (1 ≤ N ≤ 100000), далее следуют N команд, каждая в своей строке. Команда может иметь формат: “0 <число>” или “1”, обозначающий, соответственно, операции Insert(<число>) и Extract. Гарантируется, что при выполенении команды Extract в структуре находится по крайней мере один элемент.

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

Дерево отрезков, RSQ, RMQ Куча

✓ 1✗ 0—Войти и решать

Подстроки подпоследовательностей#38509

Назовем подпоследовательностью массива a непустой массив b такой, что он может быть получен из массива a удалением нескольких (возможно, никаких) элементов массива a. Например, массив [1,3] является попоследовательностью массива [1,2,3] , но [3,1] не является.

Назовем подотрезком массива a непустой массив b такой, что он может быть получен путем удаления нескольких (возможно, никаких) первых и последних элементов массива a. Например, [1,2] является подотрезком массива [1,2,3] , а [1,3] не является. Несложно заметить, что у массива длины n ровно $ {n(n+1) \over 2}$ подотрезков.

Назовем массив a длины n возрастающим , если для любого 1 ≤ i ≤ n выполняется a_i ≤ a_i+1.

Монотонностью массива назовем количество его возрастающих подотрезков.

Дан массив a длины n. Посчитайте сумму монотонностей по всем его подпоследовательностям. Так как ответ может быть очень большим, выведите его по модулю 10⁹+7.

Входные данные
В первой строке задано целое число n (1 ≤ n ≤ 200000) — длина массива a.
Во второй строке заданы n целых чисел (1 ≤ a_i ≤ 200000) — элементы массива a.

Выходные данные
Выведите одно целое число — сумму монотонностей всех подпоследовательностей по модулю 10⁹+7.

Примечание
В первом тестовом примере у массива есть 7 подпоследовательностей:

У массива [1] есть ровно один подотрезок и он является возрастающим.
У массива [2] есть ровно один подотрезок и он является возрастающим.
У массива [3] есть ровно один подотрезок и он является возрастающим.
У массива [1,2] есть три подотрезка ([1], [2], [1,2] ) и все они являются возрастающими.
У массива [1,3] есть три подотрезка ([1], [3], [1,3] ) и все они являются возрастающими.
У массива [3,2] есть три подотрезка ([3], [2], [3, 2] ), но только два из них ([3] и [2] ) являются возрастающими.
У массива [1,3,2] есть шесть подотрезков ([1], [3], [2], [1,3], [3,2], [1,3,2] ) и четыре из них ([1], [3], [2], [1,3] ) являются возрастающими.

Во втором тестовом примере все возрастающие подотрезки всех подпоследовательностей имеют длину 1.

Примеры

№	Входные данные	Выходные данные
1	3 1 3 2	15
2	3 6 6 6	12

Дерево отрезков, RSQ, RMQ Дерево Фенвика Динамическое программирование Динамическое программирование: один параметр

✓ 1✗ 1—Войти и решать

Load Balancing#29545

Коровы Фермера Джона стоят в различных точках (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

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

✓ 3✗ 251 100средняяВойти и решать

Двоичное дерево поиска 1#23571

Реализуйте сбалансированное двоичное дерево поиска.
ВНИМАНИЕ! Пользоваться vector и set из STL СТРОГО ЗАПРЕЩЕНО, однако рекомендуется стрессить ваше решение с ними для поиска багов.

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

В первой строке дано число n - количество операций с деревом. 1 <= n <= 100000.

Далее дается n строк – операции с деревом. В каждой строке находится одна из следующих операций:

1) insert x – добавить в дерево ключ x. Если ключ x уже в дереве, то ничего делать не нужно.

2) delete x – удалить из дерева ключ x. Если ключа x в дереве нет, то ничего делать не нужно.

3) exists x – если ключ х есть в дереве, то выведите “true”, иначе “false”.

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

Выведите последовательно результат выполнения всех операций exists. Каждый ответ нужно выводить в отдельной строке.

Пример:

Ввод	Вывод
6 insert 2 insert 5 insert 3 exists 3 exists 4 delete 5	true false

Двоичное дерево поиска Декартово дерево

✓ 18✗ 631 000средняяВойти и решать

Река#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

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

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

✓ 2✗ 41 200средняяВойти и решать

Why Did the Cow Cross the Road III#90431

Фермер Джон продолжает исследование переходов коров через дорогу, описанную в двух предыдущих задачах. Теперь он считает дружественными породы коров $a$ и $b$, если if $|a - b| \leq K$, и недружественными в противном случае.

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

ФОРМАТ ВВОДА (файл friendcross.in):

Первая строка ввода содержит $N$ ($1 \leq N \leq 100,000$) и $K$ ($0 \leq K < N$). Следующие $N$ строк описывают порядок по номерам пород, полей на первой стороне дороги. Каждый номер породы - это число в интервале $1 \ldots N$. Последние $N$ строк описывают порядок по номерам пород, полей на второй стороне дороги. Каждый номер породы появится ровно один раз с каждом порядке.

ФОРМАТ ВВОДА (файл friendcross.out):

Выведите максимальное количество недружественных пересекающихся пар пород.

Дерево отрезков, RSQ, RMQ

—Войти и решать

Promotion Counting#90397

Коровы, последовательно пронумерованные $1 \ldots N$ ($1 \leq N \leq 100,000$), организовали компанию в виде дерева, где корова 1 - президент (корень дерева). Каждая корова, кроме президента, имеет ровно одного менеджера (её родитель в дереве). Каждая корова $i$ имеет различный професиональный рейтинг $p(i)$, который описывает насколько хорошо она делает свою работу. Если корова $i$ есть менеджер коровы $j$, то мы говорим, что корова $j$ подчиняется корове $i$.

К несчастью коровы обнаружили что часто бывает так, что менеджер имеет меньший уровень профессиональности, чем некоторые из его подчинённых. В этом случае менеджер должен рассмотреть продвижение этих подчинённых. Ваша задача - помочь коровам узнать, когда это случается. Для каждой коровы $i$ в компании вычислите количество подчинённых $j$ таких, что $p(j) > p(i)$.

ФОРМАТ ВВОДА (файл promote.in):

Первая строка ввода содержит $N$.

Следующие $N$ строк ввода содержат рейтинги профессиональности коров $p(1) \ldots p(N)$. Все числа - различные целые в интервале $1 \ldots 1,000,000,000$.

Следующие $N-1$ строк описывают менеджера (родителя) для коров $2 \ldots N$. Напомним что у коровы 1 нет менеджера, поскольку она президент.

ФОРМАТ ВЫВОДА (файл promote.out):

Выведите $N$ строк. $i$-ая строка вывода должна говорить количество подчинённых коровы $i$ с рейтингом профессиональности большим чем у коровы $i$.

Дерево отрезков, RSQ, RMQ

—Войти и решать

Balanced Photo#90393

Фермер Джон выстроил свои $N$ коров в ряд, чтобы сделать фото. ($1 \leq N \leq 100,000$). Высота $i$-ой коровы в этой последовательности равна $h_i$, и все эти высоты различны.

ФД хочет, чтобы фотография получилась красивее. Он считает, что корова $i$ выглядит несбалансированно, если $L_i$ и $R_i$ отличаются более чем в 2 раза. Здесь $L_i$ и $R_i$ - количества коров, которые выше чем корова $i$, слева и справа соответственно. То есть, корова $i$ является несбалансированной, если большее из чисел $L_i$ и $R_i$ строго более чем в 2 раза больше, чем меньшее из этих двух чисел.

Вычислите сколько всего есть несбалансированных коров.

ФОРМАТ ВВОДА (файл bphoto.in):

Первая строка ввода содержит число $N$. Следующие $N$ строк содержат $h_1 \ldots h_N$, каждое неотрицательное целое не более чем 1,000,000,000.

ФОРМАТ ВЫВОДА (файл bphoto.out):

Выведите количество несбалансированных коров.

Дерево отрезков, RSQ, RMQ

—Войти и решать

Counting Haybales#90344

Ферма Джона состоит из $N$ полей в ряд последовательно пронумерованных $1 \ldots N$. На каждом поле может быть произвольное количество стогов сена. Инструкции ФД бывают трёх видов:

1) Добавить один стог к каждому полю в указанном интервале

2) Определить минимальное количество стогов сена внутри указанного непрерывного интервала полей.

3) Посчитать суммарное количество стогов сена внутри указанного непрерывного интервала.

ФОРМАТ ВВОДА (файл haybales.in):

Первая строка содержит два положительных целых числа $N$ ($1 \leq N \leq 200,000$) и $Q$ ($1 \leq Q \leq 100,000$).

Следующая строка содержит $N$ неотрицательных целых чисел, каждое не более, чем 100,000, указывающих, сколько стогов сена было изначально на каждом поле.

Каждая из следующих $Q$ строк содержит одну большую латинскую букву M, P или S, за которой следуют два положительных целых числа $A$ and $B$ ($1 \leq A \leq B \leq N$), или три положительных целых числа $A$, $B$, and $C$ ($1 \leq A \leq B \leq N$; $1 \leq C \leq 100,000$). 3 числа будет только в том случае, если первая буква P.

Если первая буква M выведите минимальное количество стогов сена в интервале полей $A \ldots B$.

Если первая буква P, добавьте по $C$ стогов сена в каждое поле в интервале $A \ldots B$.

Если первая буква S, выведите суммарное количество стогов сена в интервале полей $A \ldots B$.

ФОРМАТ ВЫВОДА (файл haybales.out):

Строка в выводе должна появится в ответ на каждый запрос вида M или S.

Дерево отрезков, RSQ, RMQ

—Войти и решать

The Best Subsequence#90289

п»ї

РЈ Р¤РµСЂРјРµСЂР° Р”Р¶РѕРЅР° РµСЃС‚СЊ РґРІРѕРёС‡РЅР°СЏ СЃС‚СЂРѕРєР° РґР»РёРЅРѕР№ $N$ $(1 \leq N \leq 10^9)$, РёР·РЅР°С‡Р°Р»СЊРЅРѕ РёР· РѕРґРЅРёС… РЅСѓР»РµР№.

РЎРЅР°С‡Р°Р»Р° РѕРЅ РІС‹РїРѕР»РЅРёС‚ $M$ ($1 \leq M \leq 2 \cdot 10^5$) РёР·РјРµРЅРµРЅРёР№ СЃС‚СЂРѕРєРё РїРѕ РїРѕСЂСЏРґРєСѓ. РљР°Р¶РґРѕРµ РёР·РјРµРЅРµРЅРёРµ РїРµСЂРµРІРѕСЂР°С‡РёРІР°РµС‚ РєР°Р¶РґС‹Р№ СЃРёРјРІРѕР» РѕС‚ $l$ РґРѕ $r$. РўРѕ РµСЃС‚СЊ $0$ РёР·РјРµРЅСЏРµС‚СЃСЏ РЅР° $1$ Рё РЅР°РѕР±РѕСЂРѕС‚.

Р—Р°С‚РµРј РѕРЅ Р·Р°РґР°С‘С‚ Р’Р°Рј $Q$ ($1 \leq Q \leq 2 \cdot 10^5$) РІРѕРїСЂРѕСЃРѕРІ. Р”Р»СЏ РєР°Р¶РґРѕРіРѕ РІРѕРїСЂРѕСЃР° Р’С‹ РґРѕР»Р¶РЅС‹ РІРІРµСЃС‚Рё Р»РµРєСЃРёРєРѕРіСЂР°С„РёС‡РµСЃРєРё РЅР°РёР±РѕР»СЊС€СѓСЋ РїРѕРґРїРѕСЃР»РµРґРѕРІР°С‚РµР»СЊРЅРѕСЃС‚СЊ РґР»РёРЅС‹ $k$ СЃРѕСЃС‚РѕСЏС‰СѓСЋ РёР· СЃРёРјРІРѕР»РѕРІ РїРѕРґСЃС‚СЂРѕРєРё РѕС‚ $l$ РґРѕ $r$. Р•СЃР»Рё Р’Р°С€ РѕС‚РІРµС‚ - РґРІРѕРёС‡РЅР°СЏ СЃС‚СЂРѕРєР° $s_1s_2 \dots s_k$, РІС‹РІРµРґРёС‚Рµ $\sum_{i=0}^{k-1} 2^i \cdot s_{k-i}$ (С‚Рѕ РµСЃС‚СЊ СЃС‚СЂРѕРєР° РёРЅС‚РµСЂРїСЂРµС‚РёСЂСѓРµС‚СЃСЏ РєР°Рє РґРІРѕРёС‡РЅРѕРµ С‡РёСЃР»Рѕ) РїРѕ РјРѕРґСѓР»СЋ $10^9+7$.

РџРѕРґРїРѕСЃР»РµРґРѕРІР°С‚РµР»СЊРЅРѕСЃС‚СЊ СЌС‚Рѕ СЃС‚СЂРѕРєР°, РєРѕС‚РѕСЂР°СЏ РјРѕР¶РµС‚ Р±С‹С‚СЊ РїРѕР»СѓС‡РµРЅР° РёР· РґСЂСѓРіРѕР№ СЃС‚СЂРѕРєРё СѓРґР°Р»РµРЅРёРµРј (РёР»Рё РЅРµ СѓРґР°Р»РµРЅРёРµРј) СЃРёРјРІРѕР»РѕРІ Р±РµР· РёР·РјРµРЅРµРЅРёСЏ РїРѕСЂСЏРґРєР° РѕСЃС‚Р°РІС€РёС…СЃСЏ СЃРёРјРІРѕР»РѕРІ.

РќР°РїРѕРјРЅРёРј, С‡С‚Рѕ СЃС‚СЂРѕРєР° $A$ Р»РµРєСЃРёРєРѕРіСЂР°С„РёС‡РµСЃРєРё Р±РѕР»СЊС€Рµ С‡РµРј СЃС‚СЂРѕРєР° $B$ С‚Р°РєРѕР№ Р¶Рµ РґР»РёРЅС‹ РµСЃР»Рё Рё С‚РѕР»СЊРєРѕ РµСЃР»Рё РІ РїРµСЂРІРѕР№ РїРѕР·РёС†РёРё $i$, РµСЃР»Рё РѕРЅР° СЃСѓС‰РµСЃС‚РІСѓРµС‚, $A_i \neq B_i$, РІС‹РїРѕР»РЅСЏРµС‚СЃСЏ $A_i > B_i$.

Р¤РћР РњРђРў Р’Р’РћР”Рђ (СЃ РєР»Р°РІРёР°С‚СѓСЂС‹ / stdin):

РџРµСЂРІР°СЏ СЃС‚СЂРѕРєР° СЃРѕРґРµСЂР¶РёС‚ $N$, $M$, $Q$.

РЎР»РµРґСѓСЋС‰РёРµ $M$ СЃС‚СЂРѕРє СЃРѕРґРµСЂР¶Р°С‚ РїРѕ РґРІР° С†РµР»С‹С… С‡РёСЃР»Р° $l$ Рё $r$ ($1 \leq l \leq r \leq N$) РєРѕРЅРµС‡РЅС‹Рµ С‚РѕС‡РєРё РѕР±РЅРѕРІР»РµРЅРёСЏ.

РЎР»РµРґСѓСЋС‰РёРµ $Q$ СЃС‚СЂРѕРє СЃРѕРґРµСЂР¶Р°С‚ РїРѕ С‚СЂРё С†РµР»С‹С… С‡РёСЃР»Р°, $l$, $r$, $k$ ($1 \leq l \leq r \leq N, 1 \leq k \leq r - l + 1$) вЂ”

Р¤РћР РњРђРў Р’Р«Р’РћР”Рђ (РЅР° СЌРєСЂР°РЅ / stdout):

Р’С‹РІРµРґРёС‚Рµ $Q$ СЃС‚СЂРѕРє. $i$-Р°СЏ СЃС‚СЂРѕРєР° РґРѕР»Р¶РЅР° СЃРѕРґРµСЂР¶Р°С‚СЊ РѕС‚РІРµС‚ РЅР° $i$-С‹Р№ Р·Р°РїСЂРѕСЃ.

РџР Р�РњР•Р Р’Р’РћР”Рђ:

РџР Р�РњР•Р Р’Р«Р’РћР”Рђ:

РџРѕСЃР»Рµ РІС‹РїРѕР»РЅРµРЅРёСЏ $M$ РѕРїРµСЂР°С†РёР№, СЃС‚СЂРѕРєР° С‚Р°РєРѕРІР°: $10101$.

Р”Р»СЏ РїРµСЂРІРѕРіРѕ Р·Р°РїСЂРѕСЃР° - РґР»РёРЅС‹ $5$ РѕС‚РІРµС‚ РІСЃСЏ СЃС‚СЂРѕРєР° $10101$, РєРѕС‚РѕСЂР°СЏ РёРЅС‚РµСЂРїСЂРµС‚РёСЂСѓРµС‚СЃСЏ РєР°Рє $1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 21$.

Р”Р»СЏ РІС‚РѕСЂРѕРіРѕ Р·Р°РїСЂРѕСЃР°, СЃСѓС‰РµСЃС‚РІСѓРµС‚ $5$ СѓРЅРёРєР°Р»СЊРЅС‹С… РїРѕРґРїРѕСЃР»РµРґРѕРІР°С‚РµР»СЊРЅРѕСЃС‚РµР№ РґР»РёРЅС‹ $4$: $0101$, $1101$, $1001$, $1011$, $1010$. Р›РµРєСЃРёРєРѕРіСЂР°С„РёС‡РµСЃРєРё РЅР°РёР±РѕР»СЊС€Р°СЏ РёР· РЅРёС… $1101$, РєРѕС‚РѕСЂР°СЏ РёРЅС‚РµСЂРїСЂРµС‚РёСЂСѓРµС‚СЃСЏ РєР°Рє $1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1\cdot 2^0 = 13$.

Р”Р»СЏ С‚СЂРµС‚СЊРµР№ СЃС‚СЂРѕРєРё Р»РµРєСЃРёРєРѕРіСЂР°С„РёС‡РµСЃРєРё РЅР°РёР±РѕР»СЊС€Р°СЏ РїРѕСЃР»РµРґРѕРІР°С‚РµР»СЊРЅРѕСЃС‚СЊ $111$, РєРѕС‚РѕСЂР°СЏ РёРЅС‚РµСЂРїСЂРµС‚РёСЂСѓРµС‚СЃСЏ РєР°Рє $7$.

РџР Р�РњР•Р Р’Р’РћР”Рђ:

9 1 1
7 9
1 8 8

РџР Р�РњР•Р Р’Р«Р’РћР”Рђ:

РџР Р�РњР•Р Р’Р’РћР”Рђ:

30 1 1
1 30
1 30 30

РџР Р�РњР•Р Р’Р«Р’РћР”Рђ:

73741816

РќРµ Р·Р°Р±СѓРґСЊС‚Рµ РІС‹РІРѕРґРёС‚СЊ РѕС‚РІРµС‚ РїРѕ РјРѕРґСѓР»СЋ $10^9+7$.

РћР¦Р•РќР�Р’РђРќР�Р•:

РўРµСЃС‚ 4: $N \leq 10, Q \leq 1000$
РўРµСЃС‚ 5: $M \leq 10$
РўРµСЃС‚С‹ 6-7: $N, Q \leq 1000$
РўРµСЃС‚С‹ 8-12: $N \leq 2 \cdot 10^5$
РўРµСЃС‚С‹ 13-20: РќРµС‚ РґРѕРїРѕР»РЅРёС‚РµР»СЊРЅС‹С… РѕРіСЂР°РЅРёС‡РµРЅРёР№.

РђРІС‚РѕСЂ: Chongtian Ma

Дерево отрезков, RSQ, RMQ

—Войти и решать

Identity Theft#90279

**Замечание: Время на тест и ограничение по памяти для этой задачи 3сек и 512MB, что, соответственно, в 1.5 и 2 раза больше чем по умолчанию.**

Каждая из $N$ ($1 \leq N \leq 10^5$) коров Фермера Джона имеет свой ID-номер в виде битовой строки (строки соcтоящей из символов '0' и '1'). Беси, старейшая корова, помнит ID-номера всех коров и любит спрашивать у коров их ID-номера.

Когда у коровы спрашивают ID-номер, они начинают отвечать правильную битовую строку, но могут забыть и остановиться, не закончив её. Когда Беси слышит битовую строку, если та не является ID-номером ни одной коровы на ферме, она пожимает плечами и уходит. Однако если это ID-номер другой коровы на ферме, она предполагает, что произошла кража личных данных и закрывает ферму на карантин. Заметим, что это может случиться даже если корова говорит свой полный правильный ID-номер.

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

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит $N$, количество коров на ферме у ФД.

Далее следуют $N$ строк. $k$-я строка содержит битовую строку, равную ID-номеру $k$-ой коровы.

Никакой и ID-номеров не пустой, и общая длина всех ID-номеров не более $10^6$.

ФОРМАТ ВЫВОДА (на экран / stdout):

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

Бор

—Войти и решать

Pareidolia#90230

**Примечание. Ограничение по времени для этой задачи составляет 4 секунды, что в два раза больше, чем по умолчанию. Ограничение по памяти для этой задачи составляет 512 МБ, вдвое больше, чем по умолчанию.**

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

Дана строка $s$, пусть $B(s)$ представляет собой максимальное количество повторяющихся копий. из «bessie» можно получить, удалив ноль или более символов из $s$. В приведенном выше примере $B($"bqessiyexbesszieb"$) = 2$. Кроме того, учитывая строка $t$, пусть $A(t)$ представляет собой сумму $B(s)$ по всем непрерывным подстроки $s$ строки $t$.

У фермера Джона есть строка $t$ длины не более $2\cdot 10^5$, состоящая только из символов a-z. Пожалуйста, рассчитайте $A(t)$ и как $A(t)$ изменится после $U$ ($1\le U\le 2\cdot 10^5$) обновлений, каждое из которых изменяет символ $t$. Обновления являются кумулятивными.

ФОРМАТ ВВОДА (ввод поступает с терминала/стандартного ввода):

Первая строка ввода содержит $t$.

Следующая строка содержит $U$, за которыми следуют строки по $U$, каждая из которых содержит позицию $p$ ($1\le p\le N$) и символ $c$ в диапазоне от a до z, что означает, что $p$-й символ $t$ заменяется на $c$.

ФОРМАТ ВЫВОДА (вывод на терминал / стандартный вывод):

Выведите $U+1$ строк — общее количество «bessie», которое можно сделать во всех подстроках $t$ перед любыми обновлениями и после каждого обновления.

Дерево отрезков, RSQ, RMQ дп реализация

—Войти и решать

Haircut#90116

Фермер Джон решил постричься. У него есть $N$ прядей волос ($1\le N\le 10^5$), расположенных последовательно. Прядь $i$ имеет изначально длину $A_i$ микрометров ($0\le A_i\le N$). В идеале ФД хочет, чтобы его пряди монотонно возрастали по длине. Поэтому он определил "негодность" волос как количество инверсий то есть пар $(i,j)$ таких, что $i < j$ и $A_i > A_j$.

Для каждого $j=0,1,\ldots,N-1$, ФД хочет узнать "негодность" его волос если все пряди с длиной больше чем $j$ будут уменьшены до длины ровно $j$.

ФОРМАТ ВВОДА (файл haircut.in):

Первая строка содержит $N$.

Вторая строка содержит $A_1,A_2,\ldots,A_N.$

ФОРМАТ ВЫВОДА (файл haircut.out):

Для каждого $j=0,1,\ldots,N-1$, выведите "негодность" волос ФД в новой строке.

Заметим, ответы могут потребовать 64-битного типа данных (например, "long long" в C/C++).

Дерево отрезков, RSQ, RMQ

—Войти и решать

Cow Land#90051

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

Всего имеется $N$ различных аттракционов ($2 \leq N \leq 10^5$). Определённые пары аттракционов связаны дорожками, которых всего $N-1$ штук, таким образом, что существует единственный путь, состоящий из различных дорожек между любыми двумя аттракционами. Каждый аттракцион $i$ имеет целую величину удовольствия $e_i$, которая может измениться в течение дня, поскольку некоторые аттракционы более привлекательны утром, а некоторые - вечером.

Корова, которая проходит от аттракциона $i$ до аттракциона $j$ получает удовольствие всех аттракционов маршрута от $i$ до $j$. Забавно, что общее удовольствие от всего маршрута вычисляется как побитовое XOR всех удовольствий в течение маршрута, включая удовольствия в аттракционах $i$ и $j$.

Помогите коровам определить величины удовольствий маршрутов, которые коровы собираются пройти в CowLand.

ФОРМАТ ВВОДА (файл cowland.in):

Первая строка ввода содержит $N$ и количество запросов $Q$ ($1 \leq Q \leq 10^5$). Следующая строка содержит $e_1 \ldots e_N$ ($0 \leq e_i \leq 10^9$). Каждая из следующих $N-1$ строк описывает дорожку в терминах двух номеров целочисленных аттракционов $a$ и $b (оба в интервале $1 \ldots N$). Наконец, каждая последних $Q$ строк описывает или изменение одной из величин $e_i$ или запрос на удовольствие от маршрута. Строка вида "1 $i$ $v$" означает, что величину $e_i$ нужно изменить на значение $v$ ($e_i$ should be updated to value $v$). Строка вида "2 $i$ $j$" это запрос на удовольствие от маршрута, соединяющего аттракционы $i$ и $j$.

В тестах не более 50% не будет изменений удовольствий на аттракционах.

ФОРМАТ ВЫВОДА (файл cowland.out):

Для каждого запроса вида "2 $i$ $j$", выведите одну строку - удовольствие от маршрута от $i$ к $j$.

Дерево отрезков, RSQ, RMQ

—Войти и решать

Bessie's Snow Cow#90042

Снег выпал на ферме, и Беси лепит из него снежную корову. Причём Беси хочет, чтобы та выглядела как можно более натурально. Но в этом году она лепит фигуру в виде дерева, состоящего из $N$ снежков $(1\le N\le 10^5)$ соединённых $N-1$ ветками, каждая из которых соединяет пару снежков так, что имеется уникальный путь между каждой парой снежков.

Беси добавила нос к одному из снежков, поэтому он представляет собой голову этой абстрактной снежной коровы. Она обозначила это снежок числом 1. Чтобы усилить визуальный эффект, она планирует покрасить некоторые из снежков различными цветами. Цвета обозначаются числами в интервале $1 \ldots 10^5$, и у Беси неограниченное количество красок всех цветов.

Когда Беси красит снежок в определённый цвет, все снежки в его поддереве также красятся в этот же цвет. (Снежок $y$ находится в поддереве снежка $x$, если $x$ находится на пути от $y$ к головному снежку). Занимаясь покраской, Беси обеспечивает, чтобы все цвета, которыми она красила снежки, оставались видимыми. Например, если у снежка есть цвета $[1,2,3]$ и Беси красит цветом $4$, на снежке останутся следы цветов $[1,2,3,4]$.

После некоторого количества раскрашиваний, Беси хочет узнать, как раскрашена часть её коровы. Полнота цветов("colorfulness") снежка $x$ равно количеству различных цветов $c$, которыми раскрашен этот снежок $x$. Если Беси спросит Вас о снежке $x$, Вы должны ответить сумму полноты цветов всех снежков в поддереве $x$.

Помогите Беси определить полноту цветов в определённые моменты времени.

ОЦЕНИВАНИЕ:

$Q$ определено ниже.

Тесты 2-3 удовлетворяют $N\le 10^2, Q\le 2\cdot 10^2.$
тесты 4-6 удовлетворяют $N\le 10^3, Q\le 2\cdot 10^3.$

ФОРМАТ ВВОДА (файл snowcow.in):

Первая строка содержит $N$, и количество запросов $Q$ ($1\le Q\le 10^5$).

Каждая из последующих $N-1$ строк содержит два разделённых одиночным пробелом целых числа $a$ и $b$, описывающих ветки, соединяющие снежки $a$ и $b$ ($1 \le a, b \le N$).

Каждая из последних $Q$ строк содержит запрос. Запрос имеет вид

1 x c

и означает. что Беси закрасила цветом $c$ снежок $x$ и всё его поддерево. Строка вида

2 x

Это запрос на сумму "полноцветностей" всех снежков в поддереве $x$. $1\le x\le N$ и $1\le c\le 10^5.$

ФОРМАТ ВЫВОДА (файл snowcow.out):

Для каждого запроса типа 2, выведите сумму "полноцветностей" соответствующего поддерева. Заметим. что Вы должны использовать 64-ное целое, чтобы избежать переполнения.

Дерево отрезков, RSQ, RMQ

—Войти и решать

Milk Visits#90040

Фермер Джон планирует построить $N$ ($1 \leq N \leq 10^5$) ферм, которые будут соединены $N-1$ дорогой, формируя дерево (то есть каждая ферма достижима от каждой, и нет циклов). Каждая ферма содержит корову целого типа $T_i$ между $1$ и $N$ включительно.

$M$ друзей ФД ($1 \leq M \leq 10^5$) часто его посещают. Во время визита друга $i$, ФД вместе с ним путешествует по уникальному пути от фермы $A_i$ до фермы $B_i$ (возможно $A_i = B_i$). Дополнительно, они пробуют молоко каждой коровы на своём пути. Поскольку друзья ФД также фермеры, они имеют сильное предпочтение по молоку. Каждый из них пьёт молоко только определённого типа коров. Любой из друзей ФД будет счастливым, только если сможет попить свой предпочитаемый тип молока во время пути.

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

ОЦЕНИВАНИЕ:

Тест 2 второй пример, приведенный ниже.
Тест 3 удовлетворяет $N\le 10^3, M\le 2\cdot 10^3$.
Тесты 4-7 удовлетворяют $C_i\le 10$ ($C_i$ определено ниже).

ФОРМАТ ВВОДА (файл milkvisits.in):

Первая строка ввода содержит числа $N$ и $M$.

Вторая строка ввода содержит $N$ разделённых целых чисел $T_1,T_2,\ldots, T_N$. Тип коровы на $i$-ой ферме обозначен $T_i$.

Каждая из последующих $N-1$ строк содержит два различных целых числа $X$ и $Y$ ($1 \leq X, Y \leq N$), указывающих, что имеется дорожка между фермами $X$ и $Y$.

Последующие $M$ строк содержат целые числа $A_i$, $B_i$, $C_i$. $A_i$ и $B_i$ представляют конечные точки пути во время визита $i$-ого друга, $C_i$ ($1\le C_i\le N$) указывает тип молока, предпочитаемый этим другом.

ФОРМАТ ВЫВОДА (файл milkvisits.out):

Выведите двоичную строку длины $M$. $i$-ый символ этой строки должен быть '1', если $i$-ый друг будет счастлив, иначе - '0'.

графы Дерево отрезков, RSQ, RMQ Деревья

—Войти и решать

Train Tracking#90032

Каждое утро экспресс-поезд следует от фермы в город, а каждый вечер он возвращается.

Беси знает, что у поезда есть $N$ вагонов($1 \leq N \leq 10^6$), последовательно пронумерованных $0 \dots N-1$. Вагон $i$ имеет ID номер $c_i$, написанный на нём ($0 \le c_i \le 10^9$). Все номера видны и утром, и вечером, поэтому номер каждого вагона можно увидеть два раза. Когда поезд едет утром, Беси видит вагоны в таком порядке $c_0$, $c_1$, ... $c_{N-1}$. Когда поезд едет вечером, Беси видит их в том же порядке: $c_0$, $c_1$, ... $c_{N-1}$.

Беси выбрала целое число $K$ ($1 \leq K \leq N$), и она хочет определить минимальный ID-номер для каждого непрерывного множества из $K$ вагонов. У Беси есть ноутбук, на котором она может производить вычисления. Но он довольно маленький, а её копыта - большие. Например, она не может написать все $N+1-K$ минимумов. Беси мычит ответы, после того, как вычислит их.

Поезд скоро прибудет, Помогите Беси определить $N + 1 - K$ минимумов когда поезд проезжает дважды, будьте уверены , что она использует свой ноутбук эффективно. Её ноутбук поделен на $5500$ секций, последовательно пронумерованных $0 \dots 5499$, и каждая секция имеет место, чтобы хранить ровно одно целое число из интервала $-2^{31}$ ... $2^{31}-1$ включительно. Изначально в каждой секции хранится число $0$.

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

void helpBessie(int ID);

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

Ваша реализация функции $\texttt{helpBessie}$ должна вызывать следующие функции:

int get(int index): получает значение целого числа, которое хранится в ноубуке беси в данной ячейке index.
void set(int index, int value): устанавливает значение целым числом value в ячейке index
void shoutMinimum(int output): говорит Беси промычать данное число
int getTrainLength(): возвращает $N$, количество вагонов поезда.
int getWindowLength(): возвращает $K$, длину окна.
int getCurrentCarIndex(): возвращает индекс вагона, который сейчас проходит.
int getCurrentPassIndex(): возвращает $0$ если Беси наблюдает утренний поезд и $1$, если Беси наблюдает вечерний поезд.

Чтобы помочь Вам начать писать свой код, мы даём начальные шаблоны для C/C++ и Java. Python и Pascal не поддерживаются в этой задаче.

Минимумы окон должны выводится в таком порядке, что минимум из вагонов $0, 1, \dots, K-1$ нужно вывести раньше чем минимум вагонов $1, 2, \dots, K$ и т.д. Но помимо этого ограничения упорядочения,Ваша функция может выводить минимумы во время любого из её вызовов, в любое время. Например, Ваша функция может не выводить ответов во время некоторых вызовов или выводить множество ответов во время других вызовов.

Беси имеет фантастическую кратковременную память, по этой причине нет ограничения на использование памяти в функции $\texttt{helpBessie}$ кроме обычного на 256 Мбт. Однако между вагонами Беси не способна помнить ничего не содержащегося в её ноутбуке. Поэтому между вызовами функции, Ваша программа не может хранить состояния - а только использовать вызовы $\texttt{get}$ и $\texttt{set}$ calls.

Это означает:

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

Общее количество вызовов $\texttt{set}$ плюс общее количество вызовов $\texttt{get}$, сделанные Вашей программой должны быть ограничены $25 \cdot 10^6$ для каждого теста.

Дерево отрезков, RSQ, RMQ

—Войти и решать

Disruption#90030

Ферма Джона состоит из $N$ пастбищ ($2 \leq N \leq 50,000$), попарно соединённых $N-1$ двунаправленными дорожками единичной длины. Известно также, что имеется путь из любого пастбища к любому.

Однако если одну из дорожек заблокировать, то ферма разделится на две части, внутри каждой из которых связность сохранится, а между ними - нет. Поэтому ФД строит $M$ дополнительных дорожек ($1 \leq M \leq 50,000$), каждая из которых имеет положительную целую длину не более $10^9$. Коровы пользуются исходными дорожками, пока это возможно.

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

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

ФОРМАТ ВВОДА (файл disrupt.in):

Первая строка ввода содержит $N$ и $M$. Каждая из последующих $N-1$ строк описывает оригинальную дорожку целыми числами $p$ $q$, где $p$ \neq q$ - пастбища, соединённые этой дорожкой (в интервале $1 \ldots N$). Каждая из оставшихся $M$ строк описывает дополнительную дорожку тремя целыми числами $p$, $q$, $r$, где $r$ длина этой дорожки. Не более одной дорожки пролегает между любыми двумя пастбищами.

ФОРМАТ ВЫВОДА (файл disrupt.out):

Для каждой из $N-1$ оригинальных дорожек, в порядке как они появились на вводе, выведите длину кратчайшей "замещающей" дорожки, которая восстановит связность фермы в результате блокировки оригинальной дорожки. Если такой дорожки не существует, выведите -1.

Двоичные подьемы Дерево отрезков, RSQ, RMQ

—Войти и решать

Auto-Complete#89922

Problem 1: Auto-complete [Traditional]
У Беси есть новый мобильный телефон, и она любит посылать текстовые сообщения, хотя она часто совершает ошибки набора. Фермер Джон написал для неё приложение, которое автоматически дополняет набранную часть слова до полного слова.
Это приложение имеет доступ к словарю из W слов, каждое из которых состоит из маленьких латинских букв a..z. Общее количество букв во всех словах не превышает 1,000,000. На ввод этому приложению подаётся список из N частичных слов (1<=N<=1000), каждое из которых состоит не более чем из 1000 символов - маленьких латинских букв. Для каждого частичного слова I, также задаётся число K_i, которое означает, что приложение должно найти K_i-ое слово в алфавитном порядке, для которого частичное слово I является префиксом. То есть, если упорядочить все корректные дополнения i-го частичного слова, то приложение должно вывести K_i-ое слово в этой последовательности.
PROBLEM NAME: auto
Формат входных данных
* Строка 1: Два целых числа: W и N.
* Строки 2..W+1: Строка i+1: i-ое слово в словаре.
* Строки W+2..W+N+1: Строка W+i+1: Одно целое число K_i за которым через пробел следует i-ое частичное слово.
Формат выходных данных
* Строки 1..N: Строка i должна содержать индекс внутри словаря (целое число в диапазоне от 1 до W) – K_i-ое завершение (в алфавитном порядке) i-го частичного слова или -1, если имеется менее чем K_i завершений.
Примечание
Завершения a есть {aa,aaa,aab,ab,abc,ac}. 4-ое из них ab, которое перечислено под номером 3 в словаре. Завершения da есть {daa,dab,dadba}, 2-ое завершение – dab, перечисленное под номером 1 в словаре. Нет 4-го завершения строки dab.

Бор

—Войти и решать