Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 279 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 36 37 38 39 40 41 42 >> Отображать по:
#111756
Разрезание графа
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Дан неориентированный граф. Над ним в заданном порядке производят операции следующих двух типов:

  • cut — разрезать граф, то есть удалить из него ребро;
  • ask — проверить, лежат ли две вершины графа в одной компоненте связности.

Известно, что после выполнения всех операций типа cut рёбер в графе не осталось. Найдите результат выполнения каждой из операций типа ask.

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

Первая строка входного файла содержит три целых числа, разделённые пробелами — количество вершин графа n, количество рёбер m и количество операций k (1 ≤ n ≤ 50 000, 0 ≤ m ≤ 100 000, m ≤ k ≤ 150 000).

Следующие m строк задают рёбра графа; i-я из этих строк содержит два числа ui и vi (1 ≤ ui, vi ≤ n), разделённые пробелами — номера концов i-го ребра. Вершины нумеруются с единицы; граф не содержит петель и кратных рёбер.

Далее следуют k строк, описывающих операции. Операция типа cut задаётся строкой «cut u v» (1 ≤ u, v ≤ n), которая означает, что из графа удаляют ребро между вершинами u и v. Операция типа ask задаётся строкой «ask u v» (1 ≤ u, v ≤ n), которая означает, что необходимо узнать, лежат ли в данный момент вершины u и v в одной компоненте связности. Гарантируется, что каждое ребро графа встретится в операциях типа cut ровно один раз.

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

Для каждой операции ask во входном файле выведите на отдельной строке слово «YES», если две указанные вершины лежат в одной компоненте связности, и «NO» в противном случае. Порядок ответов должен соответствовать порядку операций ask во входном файле.

Примеры
Входные данные
3 3 7
1 2
2 3
3 1
ask 3 3
cut 1 2
ask 1 2
cut 1 3
ask 2 1
cut 2 3
ask 3 1
Выходные данные
YES
YES
NO
NO
#111771
Множества
  
ограничение по времени на тест
0.75 second;
ограничение по памяти на тест
128 megabytes

На вступительном экзамене по информатике в СУНЦ МГУ Вашему другу предложили реализовать структуру данных для хранения множеств чисел. Так как он специализируется на истории литературы, данную структуру придётся реализовать Вам.

Структура должна хранить m множеств чисел от 0 до n, при этом одно число может принадлежать сразу нескольким множествам.

Вы должны реализовать следующие операции на этой структуре:

  • ADD e s
    Добавить в множество №s (0 <= s <= m) число e (0 <= e <= n).

  • DELETE e s
    Удалить из множества №s (0 <= s <= m) число e (0 <= e <= n). Гарантируется, что до этого число e было помещено в множество

  • CLEAR s
    Очистить множество №s (0 <= s <= m).

  • LISTSET s
    Показать содержимое множества №s (0 <= s <= m), либо -1, если множество пусто.

  • LISTSETSOF e
    Показать множества, в которых лежит число e (0 <= e <= n), либо -1, если этого числа нет ни в одном множестве.

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

Сначала вводятся числа N (1 <= N <= 9223372036854775807), M (1 <= M <= 100000) и K (0 <= K <= 100000) — максимальное число, номер максимального множества и количество запросов к структуре данных. Далее следуют K строк указанного формата запросов.

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

На каждый запрос LISTSET Ваша программа должна вывести числа — содержимое запрошенного множества или -1, если множество пусто.

На каждый запрос LISTSETSOF Ваша программа должна вывести числа — номера множеств, содержащие запрошенное число или -1, если таких множеств не существует.

На прочие запросы не должно быть никакого вывода.

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

Примеры
Входные данные
10 10
9
ADD 1 1
ADD 1 2
ADD 2 1
LISTSET 1
LISTSETSOF 1
DELETE 1 1
LISTSET 1
CLEAR 1
LISTSET 1
Выходные данные
1 2 
1 2 
2 
-1
Входные данные
10 10
5
ADD 1 1
LISTSET 10
LISTSET 1
CLEAR 1
LISTSET 1
Выходные данные
-1
1 
-1
#111773
Военные учения
  
Темы: [Деревья]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
16 megabytes
В ходе недавних военных учений министр обороны Советской Федерации товарищ Иванов имел возможность лично убедиться в блестящей боевой готовности солдат вверенной ему Советской Армии. Но одна вещь всё же продолжала беспокоить выдающегося военачальника. Прославленный генерал понимал, что была продемонстрирована лишь физическая подготовка солдат. Теперь настало время организовать очередные учения и проверить интеллектуальные способности личного состава. Генерал Шульман, вновь назначенный ответственным за проведение учений, пожертвовал все выделенные деньги бедным и с чистой совестью лёг спать. Во сне генералу явился учебник по тактике и изложил схему, руководствуясь которой можно провести учения совершенно бесплатно.

В соответствии с этой схемой учения делятся на N раундов, в течение которых N солдат, последовательно пронумерованных от 1 до N, маршируют друг за другом по кругу, т.е. первый следует за вторым, второй за третьим, ..., (N-1)-й за N-м, а N-й за первым. В каждом раунде очередной солдат выбывает из круга и идёт чистить унитазы, а оставшиеся продолжают маршировать. В очередном раунде выбывает солдат, марширующий на K позиций впереди выбывшего на предыдущем раунде. В первом раунде выбывает солдат с номером K. Разумеется, г-н Шульман не питал никаких надежд на то, что солдаты в состоянии сами определить очерёдность выбывания из круга. «Эти неучи даже траву не могут ровно покрасить», – фыркнул он и отправился за помощью к прапорщику Шкурко.


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

Единственная строка содержит целые числа N (1 ≤ N ≤ 100000) и K (1 ≤ K ≤ N).


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

Вывести через пробел номера солдат в порядке их выбывания из круга.
Примеры
Входные данные
5 3
Выходные данные
3 1 5 2 4
#111777
Число возрастающих подпоследовательностей
  
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes

Задана последовательность из n чисел a1, a2, ..., an. Подпоследовательностью длины k этой последовательности называется набор индексов i1, i2, ..., ik, удовлетворяющий неравенствам 1 ≤ i1 < i2 < ... < ik ≤ n. Подпоследовательность называется возрастающей, если выполняются неравенства ai1 < ai2 < ... < aik.

Необходимо найти число возрастающих подпоследовательностей наибольшей длины заданной последовательности a1, ... ,an. Так как это число может быть достаточно большим, необходимо найти остаток от его деления на 109 + 7.

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

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 105). Вторая строка входного файла содержит n целых чисел: a1, a2, ... ,an. Все ai не превосходят 109 по абсолютной величине.

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

В выходной файл выведите ответ на задачу.

Примеры
Входные данные
5
1 2 3 4 5
Выходные данные
1
Входные данные
6
1 1 2 2 3 3
Выходные данные
8
#111778
Мобильные телефоны
  
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes

В области Тампере существуют станции обслуживания мобильных телефонов четвертого поколения, которые работают следующим образом. Вся область разделена на квадраты. Квадраты формируют матрицу S×S, строки и столбы которой нумеруются с 0 до S - 1. Каждый квадрат содержит одну станцию обслуживания. Количество активных мобильных телефонов внутри квадрата может меняться, потому что телефон может перемещаться из одного квадрата в другой или выключаться. Временами каждая станция обслуживания передает сведения об изменении в количестве активных телефонов на главную станцию обслуживания (вместе с номером строки и столбца матрицы).

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

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

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

Команда Параметры Значение
0 S Инициализирует матрицу размером S×S, состоящую только из нулей. Эта команда поступает один раз и является самой первой командой.
1 X Y A Добавить число A к количеству активных мобильных телефонов в квадрате (X;Y). Число A может быть как положительным, так и отрицательным.
2 L B R T Выдать текущую сумму количеств активных мобильных телефонов во всех квадратах (X;Y), где L ≤ X ≤ R, B ≤ Y ≤ T.
3   Прервать программу. Эта команда поступает один раз и является самой последней командой.

Все значения всегда лежат в правильном диапазоне, поэтому нет необходимости их проверять. В частности, если число A отрицательное, то число активных телефонов в каком-либо квадрате все равно не станет меньше нуля. Индексы начинаются с 0, поэтому, например, для таблицы размера 4×4 имеем 0 ≤ X ≤ 3, 0 ≤ Y ≤ 3.

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

Ваша программа не должна отвечать ни на какую команду, кроме 2. Если команда 2, то ваша программа должна вывести единственную строку, содержащую одно целое число — ответ на этот запрос.

Ограничения

Размер таблицы S×S 1×1 ≤ S×S ≤ 1024×1024
Значение ячейки в любой момент времени V 0 ≤ V ≤ 215 - 1 (= 32767)
Величина обновления A -215 ≤ A ≤ 215 - 1 (= 32767)
Количество команд U 3 ≤ U ≤ 60002
Максимальное количество активных телефонов во всей таблице M M = 230
Примеры
Входные данные
0 4
1 1 2 3
2 0 0 2 2
1 1 1 2
1 1 2 -1
2 1 1 2 3
3
Выходные данные
3
4
Страница: << 36 37 38 39 40 41 42 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест