Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 279 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 19 20 21 22 23 24 25 >> Отображать по:
#2863
План уничтожения
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Секретный бункер уходит на N этажей вниз. Под нижним этажом бункера находится сверхсекретная лаборатория. Злобный диверсант хочет вывести лабораторию из строя, залив её водой (даже очень небольшого количества воды хватит, чтобы запоганить сверхточные приборы). Для этого он использует лужицы воды, остающиеся от жизнедеятельности обитателей бункера. В лужицах i-го этажа находится Ei воды. Диверсанту известно, что если на нём скопится больше Сi воды, то перегородка не выдержит и вся вода сольется на этаж ниже. Он может проделать отверстия в некоторых перегородках, по которым вода также стечет вниз. Проделать отверстие в полу i-го этажа стоит Pi у.е. Помогите диверсанту уничтожить лабораторию с минимальными материальными затратами.

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

Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 500000) - количество этажей в бункере, в следующих N строках находятся тройки целых чисел Ci, Ei, Pi (0 < Ei ≤ Ci < 1000000; E1+E2+...+EN < 2000000000; Pi > 0; P1+P2+...+PN < 2000000000). Этажи нумеруются сверху вниз.

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

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

Примеры
Входные данные
4 
1 1 1 
1 1 3 
3 1 2 
3 1 10
Выходные данные
3
1
3
#2881
Подстрока
  
+ структуры данных (например, двумерное дерево интервалов)

Недавно разведка перехватила зашифрованное сообщение — строку s. Все ресурсы аналитического центра, в котором вы работаете, были брошены на его декодирование. Ваш отдел занимается шифрами нового поколения. На данный момент известно всего n таких шифров. Для каждого из них есть три характерных параметра — целые числа l, r и строка t. Пусть строка g была получена в результате применения этого метода. Тогда строка glgl+1 . . . gr−1gr (здесь gi — это i-й символ строки g) содержит t как подстроку.

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

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

Первая строка входного файла содержит строку s (1 ≤ |s| ≤ 100 000, где |s| — длина строки s).

Вторая строка входного файла содержит целое число n — количество типов шифрования (1 ≤ n ≤ 100 000). Последующие nстрок содержат по два целых числа li, ri и строку ti, разделенные пробелами — характерные параметры i-го метода шифрования (1 ≤ li ≤ ri ≤ |s|).

Все строки состоят из строчных букв латинского алфавита. Суммарная длина всех ti не превосходит 100 000.

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

Выведите одну строку — для каждого типа шифрования «+», если сообщение s могло быть получено в результате его применения, или «-» в противном случае.

Примеры
Входные данные
frommarsiam
3
6 10 i
2 11 am
1 9 human
Выходные данные
++-
#2892
Каноническое бинарное дерево
  
#2980
Откат
  
Источники: [ Командные олимпиады, ВКОШП, 2010, Задача I ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Сергей работает системным администратором в очень крупной компании. Естественно, в круг его обязанностей входит резервное копирование информации, хранящейся на различных серверах и «откат» к предыдущей версии в случае возникновения проблем.

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

На данный момент у Сергея хранятся \(n\) точек восстановления различных серверов, пронумерованных от 1 до \(n\). Точка восстановления с номером \(i\) позволяет произвести откат для сервера \(a_i\). Сергей решил разбить перенос на этапы, при этом на каждом этапе в случае возникновения проблем будут доступны точки восстановления с номерами \(l, l + 1, \ldots, r\) для некоторых \(l\) и \(r\).

Для того, чтобы спланировать перенос данных оптимальным образом, Сергею необходимо научиться отвечать на запросы: для заданного \(l\), при каком минимальном \(r\) в процессе переноса будут доступны точки восстановления не менее чем \(k\) различных серверов.

Помогите Сергею.

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

Первая строка входного файла содержит два целых числа \(n\) и \(m\) (\(1 \le n, m \le 10^5\)), разделенные пробелами — количество точек восстановления и количество серверов. Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) — номера серверов, которым соответствуют точки восстановления (\(1 \le a_i \le m\)).

Третья строка входного файла содержит \(q\) — количество запросов, которые необходимо обработать (\(1 \le q \le 100\,000\)). В процессе обработки запросов необходимо поддерживать число \(p\), исходно оно равно 0. Каждый запрос задается парой чисел \(x_i\) и \(y_i\), используйте их для получения данных запроса следующим образом: \(l_i = \left((x_i + p) \bmod n\right) + 1\),

\(k_i = \left((y_i + p) \bmod m\right) + 1\) (\(1 \le l_i,x_i \le n\), \(1\le k_i, y_i \le m\)). Пусть ответ на \(i\)-й запрос равен \(r\). После выполнения этого запроса, следует присвоить \(p\) значение \(r\).

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

На каждый запрос выведите одно число — искомое минимальное \(r\), либо 0, если такого \(r\) не существует.

Примеры
Входные данные
7 3
1 2 1 3 1 2 1
4
7 3
7 1
7 1
2 2
Выходные данные
1
4
0
6
#2983
Баржа
  
Темы: [Стек]
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
64 megabytes

На барже располагается K грузовых отсеков. В каждый отсек можно поместить некоторое количество бочек с одним из 10 000 видов топлива. Причём извлечь бочку из отсека можно лишь в случае, если все бочки, помещённые в этот отсек после неё, уже были извлечены. Таким образом в каждый момент времени в каждом непустом отсеке имеется ровно одна бочка, которую можно извлечь не трогая остальных. Будем называть такие бочки крайними.

Изначально баржа пуста. Затем она последовательно проплывает через N доков, причём в каждом доке на баржу либо погружается бочка с некоторым видом топлива в некоторый отсек, либо выгружается крайняя бочка из некоторого отсека. Однако, если указанный отсек пуст, либо если выгруженная бочка содержит не тот вид топлива, который ожидалось, следует зафиксировать ошибку. Если на баржу оказывается погружено более P бочек или если после прохождения всех доков она не стала пуста, следует также зафиксировать ошибку. От вас требуется либо указать максимальное количество бочек, которые одновременно пребывали на барже либо зафиксировать ошибку.

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

В первой строке три целых числа N, K и P (1 ≤ N, K, P ≤ 100 000). Далее следует N строк с описанием действия, выполняемого в очередном доке. Если в нём происходит погрузка, то строка имеет вид «+ A B», где A — номер отсека, в который помещается бочка, а B — номер вида топлива в ней. Если же док занимается разгрузкой, то строка имеет вид «- A B», где A — номер отсека, из которого извлекается бочка, а B — номер ожидаемого вида топлива.

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

Вывести либо одно число, равное искомому максимуму в случае безошибочного прохождения баржой маршрута, либо вывести слово «Error» в противном случае.

Примеры
Входные данные
6 1 2
+ 1 1
+ 1 2
- 1 2
- 1 1
+ 1 3
- 1 3
Выходные данные
2
Страница: << 19 20 21 22 23 24 25 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест