Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 279 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 12 13 14 15 16 17 18 >> Отображать по:
#1361
Продажа билетов
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Задано количество мест в электричке и набор запросов Xi и Yi - номера станций от которой и до которой необходим билет. Необходимо ответить, имеются ли свободные места на интервале (и продать билет) или мест нет.

В новых элитных электричках каждому пассажиру положено сидячее место. Естественно, количество сидячих мест ограничено и на всех их может не хватить. Маршрут электрички проходит через N+1 станция, занумерованные от 0 до N. Когда человек хочет купить билет, он называет два числа x и y – номера станций, откуда и куда он хочет ехать. При наличии хотя бы одного сидячего места на этом участке на момент покупки ему продается билет, иначе выдается сообщение «билетов нет» и билет не продается. Ваша задача – написать программу, обслуживающую такого рода запросы в порядке их прихода.

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

В первой строке содержаться три числа N – количество станций (1 ≤ N ≤ 200 000), K – количество мест в электричке (1 ≤ K ≤ 1000) и M – количество запросов (1 ≤ M ≤ 100 000). В следующих M строках описаны запросы, каждый из которых состоит из двух чисел x и y (0 ≤ x < y <= N).

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

На каждый запрос ваша программа должна выдавать результат в виде числа 0 если билет не продается и 1 если билет был продан. Каждый результат должен быть на отдельной строке

Примеры
Входные данные
5 2 4
0 4
1 2
1 4
2 4
Выходные данные
1
1
0
1
#1362
Острова
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Заданы острова и порядок строительства мостов между островами (мост соединяет два острова). Необходимо узнать, после строительства какого моста все острова станут связными.

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

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

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

Первая строка содержит два числа: N - число островов (1 ≤ N ≤ 100 000) и M – количество мостов в плане (1 ≤ M ≤ 200 000). В каждой следующей строке содержится описание моста – два числа x и y (0 ≤ x, y < N) – номера соединяемых островов.

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

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

Примеры
Входные данные
4 5
0 1
0 2
1 2
2 3
3 0
Выходные данные
4
#1363
Построение
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Солдаты должны быть выстроены по росту. Необходимо обрабатывать два вида команд: добавить в строй солдата с заданным ростом и удалить солдата, стоящего на заданном месте.

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

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

Первая строка содержит число N – количество команд (1 ≤ N ≤ 50 000). В каждой следующей строке содержится описание команды: число 1 и X если солдат приходит в строй (X – рост солдата, натуральное число до 100 000 включительно) и число 2 и Y если солдата, стоящим в строе на месте Y надо удалить из строя. Солдаты в строе нумеруются с нуля.

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

На каждую команду 1 (добавление в строй) вы должны выводить число K – номер позиции, на которую должен встать этот солдат (все стоящие за ним двигаются назад). Выводите числа по одному в строке.

Примеры
Входные данные
5
1 100
1 200
1 50
2 1
1 150
Выходные данные
0
0
2
1
#1364
Сугробы на ЛЭП
  
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes
Необходимо обрабатывать два вида запросов: добавить заданное число к каждой ячейке интервала и подсчитать сумму на интервале.

Служба электроснабжения проводит мониторинг уровня снега, лежащего на ЛЭП Нью-Васюки - Москва. Вся ЛЭП разбивается на участки опорами. Снег имеет свойства падать на какой-либо интервал ЛЭП, если там уже лежал какой-либо снег, то высота снежного покрова на этом участке суммируется. Также снег имеет тенденцию таять на участке трассы в результате оттепели, при этом известно, что не бывает сугробов отрицательной высоты. Энергетикам крайне важно уметь узнавать суммарную высоту снежного покрова на некоторых последовательных участках, чтобы знать вероятность обрыва проводов.

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

В первой строке входного файла содержатся два числа: N – (1 ≤ N ≤ 10 000) и M – количество команд (1 ≤ M ≤ 50 000). Каждая команда имеет вид “1 L R S”, что означает, что на участок с L-ой опоры по R-ую опору выпало S сантиметров снега (S может быть и отрицательным, тогда это означает, что такое количества снега растаяло), или “2 L R” – запрос суммарной высоты снега на участке с L-ой опоры по R-ую. Опоры нумеруются от 0 до N. Гарантируется, что для запросов вида “1 L R S” при S < 0 на каждом участке между опорами L и R уровень снега составляет не менее S.

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

На каждую команду 2 (запрос) вы должны выводить число K – суммарную высоту снежного покрова, лежащего на проводах с L-ой опоры по R-ую. Каждое число должно выводиться на новой строке. Известно, что в процессе работы суммарное количество снега на любом интервале не превышает 231.

Примеры
Входные данные
10 5
1 0 9 10
1 1 5 -3
2 4 8
1 0 6 25
2 0 2
Выходные данные
37
67
#1375
Острова
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

Первая строка содержит два числа: число островов N (1≤N≤10000) и количество мостов в плане M (1≤M≤50000). Далее идет M строк, каждая содержит два числа x и y (1≤x,y≤N) - номера городов, которые соединяет очередной мост в плане.

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

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

Примеры
Входные данные
4 5
1 2
1 3
2 3
3 4
4 1
Выходные данные
4
Страница: << 12 13 14 15 16 17 18 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест