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

332 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
My Cow Ate My Homework#89986
Вам дали длинное домашнее задание из \(N\) вопросов (\(3 \leq N \leq 100,000\)), каждый из которых оценивается баллами в интервале 0...10,000. Как это часто бывает, Ваш учитель планирует выставить финальную оценку, отбрасывая вопрос, на котором Вы получили самую низкую оценку, и находя среднюю оценку среди оставшихся. К несчастью, Беси съела Ваши ответы на первые \(K\) вопросов (\(K\) от 1 до \(N-2\))

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

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

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

Первая строка ввода содержит \(N\), а следующая строка содержит оценки по \(N\) вопросам.

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

Выведите по одлному числу в строке, все значения \(K\) при которых Вы заработаете максимальную оценку.

Префиксные суммы(минимумы, ...)
—Войти и решать
Haybale Feast#89981
Фермер Джон готовит деликатесную еду для своих коров. В его амбаре имеется \(N\) стогов сена (\(1 \le N \le 100,000\)). \(i\)-ый стог имеет опредённый вкус \(F_i\) (\(1 \le F_i \le 10^9\)) и определённую пряность \(S_i\) (\(1 \le S_i \le 10^9\)).

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

ФД хочет определить минимальную пряность, кторую можно достичь, чтобы вкус был не менее \(M\) (\(1 \le M \le 10^{18}\)).

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

Первая строка содержит целые числа \(N\) и \(M\), количество стогов сена и минимальный вкус, которого нужно достичь, соответственно. Следующие \(N\) строк описывают \(N\) стогов сена парой чисел в строке - первое вкус \(F\), а второе - пряность \(S\).

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

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

"Два указателя"Жадный алгоритмПрефиксные суммы(минимумы, ...)
—Войти и решать
Fair Photography#89950

N (2 <= N <= 100,000) коров Фермера Джона стоят в различных позициях вдоль длинной изгороди. I-ая корова стоит на позиции xi (целое число в диапазоне 0...1,000,000,000) и является либо чисто белой коровой, либо коровой с пятном. Никакие две коровы не занимают одну и ту же позицию и имеется хотя бы одна белая корова.
ФД хочет сделать фото непрерывного интервала коров, так чтобы на фото было одинаковое количество белых и пятнистых коров. ФД хочет определить максимальный размер такого фото, где размер равен разности между максимальной и минимальной позициями коров на фото.
Чтобы дать себе шанс увеличить размер фото, ФД может пририсовать пятно произвольному подмножеству белах коров, тем самым превращая их в пятнистых.
Пожалуйста, определите наибольший размер фото, которое ФД может сделать, с учётом возможности перекрашивания коров из белых в пятнистые. (Конечно, ФД может и не красить коров, если ему так выгоднее)
PROBLEM NAME: fairphoto
Формат ввода:
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит xi и либо W (для белой коровы) либо S (для пятнистой коровы).
Примечание
Всего есть 5 коров. Одна из них белая на позиции 8 и т.д.

Формат вывода:
* Строка 1: Максимальный размер фото, которое может сделать ФД с учётом возможности перекрашивания белых коров в пятнистых.


Примечание
ФД фотографирует коров с позиции 3 по позицию 10. В этом интервале имеется 4 коровы 3 белых и 1 пятнистая, поэтому он перекрасит одну корову из белых в пятнистую.

Префиксные суммы(минимумы, ...)
—Войти и решать
Fair Photography#89944

N коров (1 <= N <= 100,000) Фермера Джона стоят на различных позициях вдоль длинной прямой изгороди. I-ая корова стоит на позиции xi (целое число в диапазоне 0...1,000,000,000) и имеет породу Bi (‘G’ либо ‘H’). Никакие две коровы не занимают одну и ту же позицию.
ФД хочет сделать фото непрерывного интервала коров, но так чтобы породы были справедливо представлены на фото. Справедливо это значит, что все типы представлены одним числом, Например фото где все коровы имеют тип ‘H’ – подходит и фото где 27 ‘H’ и 27 ‘G’ тоже подходит, а фото с 10 ‘H’ и 9 ‘G’ – не подходит. Помогите ФД найти справедливое фото максимального размера. Размером фото называется разность между максимальной и минимальной позицией коров на фото. Возможно, что справедливое фото будет состоять из одной коровы, тогда ответ 0.
PROBLEM NAME: fairphoto
Формат ввода:
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит xi и bi.
Примечание
Имеется 6 коров с породами слева направо G, H, G, G, H, G.
Формат вывода:
* Строка 1: Одно целое число – максимальный размер справедливого фото.
Примечание
Наибольшее справедливое фото содержит 4 средних коровы, 2 ‘H’ и 2 ‘G’.
Префиксные суммы(минимумы, ...)
—Войти и решать
The Lazy Cow#89941

Сегодня жаркий летний день, и корова Беси чувствует себя утомлённой. Она хочет так расположиться на поле, чтобы она находилась на коротком расстоянии от как можно большего количества вкусной травы.
Поле, на котором живёт Беси, описывается решёткой N*N квадратных ячеек (1 <= N <= 400). Ячейка в строке r и колонке c (1 <= r,c <= N) содержит G(i,j) единиц травы (0 <= G(i,j) <= 1000). От своей начальной ячейки Беси хочет сделать не более K шагов (0 <= K <= 2*N). Каждый шаг – это переход в соседнюю ячейку (на север, юг, запад или восток от текущей).
Например, предположим задана такая решётка где B описывает начальную позицию Беси (строка 3, колонка 3)
50 5 25* 6 17 14 3* 2* 7* 21 99* 10* 1*(B) 2* 80* 8 7* 5* 23* 11 10 0 78* 1 9
Если K=2, то для Беси достижимы только ячейки, помеченные *.
Пожалуйста, помогите Беси определить максимальное количество травы, которое она может достичь, если выберет оптимальное положение на решётке.
PROBLEM NAME: lazy
Формат входных данных
* Строка 1: Целые числа N и K.
* Строки 2..1+N: Строка r+1 содержит N целых чисел, описывающих строку r решётки.
Формат выходных данных
Примечание
В примере выше Беси может достичь 342 единицы травы, если разместится в середине решётки.
Префиксные суммы(минимумы, ...)
—Войти и решать
The Lazy Cow#89936

Сегодня жаркий летний день, и корова Беси чувствует себя утомлённой. Она хочет так расположиться на поле, чтобы она находилась на коротком расстоянии от как можно большего количества вкусной травы.
Имеется N (1 <= N <= 100,000) участков травы на поле Беси, которое представляется числовой прямой. I-тый участок травы содержит gi единиц травы (1<=gi<=10,000) и находящихся в различных точках на расстоянии xi от начала поля (0 <= xi <= 1,000,000). Беси хочет выбрать на поле такую точку, (возможно некоторую точку из тех, что с травой), чтобы максимальное количество травы находилось на расстоянии не более K шагов от этой точки (1 <= K <= 2,000,000).
Пожалуйста, помогите Беси определить максимальное количество травы если она выберет наилучшее расположение этой точки.
PROBLEM NAME: lazy
Формат входных данных
* Строка 1: Два целых числа N и K.
* Строки 2..1+N: Строка i+1 описывает i-ый кусок травы, используя 2 Целых числа: gi и xi
Формат выходных данных
* Строка 1: Максимальное количество травы на расстоянии не превышающем K от оптимальной позиции Беси.


Примечание
Беси должна расположиться на позиции x=4, тогда количества травы, находящиеся в позициях x=1, x=2 и x=7 ,будут достижимы для неё.

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

N (1 <= N <= 50,000) коров Фермера Джона выстроились в ряд, каждая описывается своим ID породы.
Коровы одной породы рискуют поругаться, если стоят слишком близко. А именно, две коровы одной породы называются "crowded" если их позиции в ряду отличаются не более чем на K (1<=K< N).
Вычислите максимальный ID пары "crowded" коров.
PROBLEM NAME: proximity
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа: N и K.
* Строки 2..1+N: Каждая строка содержит ID породы одной коровы в ряду. Все ID коров находятся в диапазоне 0..1,000,000.

Формат выходных данных
* Строка 1: Максимальный ID породы двух "crowded" коров или -1 если нет такой пары коров.
Примечание
Имеется две пары "crowded" коров - с ID породы 3 и 4.

Префиксные суммы(минимумы, ...)
—Войти и решать
Seating#89884

Чтобы заработать немного денег, коровы открыли ресторан. В ресторане N мест (1 <= N <= 500,000) в одном ряду. Изначально, все они пусты.
В течение дня в ресторане происходят M (1 <= M <= 300,000) различных событий одного из двух типов:
1. Прибывает вечеринка размером p (1 <= p <= N). Беси хочет усаживать вечеринку на непрерывный блок из p мест. Если таких блоков несколько, то она садит вечеринку на блок с самым маленьким номером начальной позиции. Если такого блока нет, вечеринка убывает.
2. Задается диапазон [a,b] (1 <= a <= b <= N), и каждый в этом диапазоне мест, подымается и покидает ресторан.
Помогите Беси вычислит общее количество вечеринок, которые "уйдут несолоно хлебавши" в течение дня.

PROBLEM NAME: seating
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и M.
* Строки 2..M+1: Каждая строка описывает одно событие в форме "A p" (что означает прибытие вечеринки размером p) или в форме "L a b" (что означает, что все коровы в диапазоне [a,b] уходят).

Формат выходных данных
* Строка 1: Количество вечеринок, которые не начнутся.
Примечание
Вечерника #3 не сможет быть размещена. Все другие вечеринки состоятся.

Дерево отрезков, RSQ, RMQ
—Войти и решать
Optimal Milking#89864

Фермер Джон купил новый амбар, содержащий N (1 <= N <= 40,000) доильных машин, последовательно пронумерованных от 1 до N и расположенных в ряд.
Доильная машина i способна извлекать по M(i) (1 <=M(i) <= 100,000) единиц молока в день. Однако, они установлены так близко, что, если машина I используется в какой-то день, то в этот день не могут быть использованы две соседние машины (начальная и конечная машина имеют по одному соседу). ФД может выбирать различные подмножества работающих машин в различные дни.
ФД хочет вычислить максимальное количество молока, которое он может извлечь за серию из D(1 <= D <= 50,000) дней. В начале каждого дня у него есть достаточное количество времени, чтобы выполнить модификацию одной выбранной машины I, и изменить дневной выпуск молока этой машины от прошлого дня к сегодняшнему. Вам дан список этих ежедневных модификаций, определите, сколько молока может извлечь ФД в течение D дней (заметим, что это число может не вместиться в 32-битное целое).
PROBLEM NAME: optmilk
Формат входных данных
* Строка 1: Значения N и D.
* Строки 2..1+N: Строка i+1 содержит начальное значение M(i).
* Строки 2+N..1+N+D: Строка 1+N+d содержит два целых числа i и m, означающие, что ФД изменил значение M(i) на m в начале дня d.
Формат выходных данных
* Строка 1: Максимальное суммарное количество молока, которое ФД сможет произвести за D дней.
Примечание
В день 1 оптимальное количество молока 2+4 = 6 (также достижимое как 1+3+2). В день 2 оптимальное количество молока 7+4=11. В день 3 оптимальное количество молока 10+3+2=15.
Дерево отрезков, RSQ, RMQ
—Войти и решать
Concurrently Balanced Strings#89847

Коровы Фермера Джона различаются по породам и каждая корова помечена гигантским пятном на боку в виде круглой скобки. В зависимости от направления, в котором смотрит корова, эта скобка может быть левой или правой скобкой.
Однажды утром ФД организовал своих коров в K строк по N коров в каждой строке (1 <= K <= 10, 1 <= N <= 50,000). Коровы смотрят в произвольных направлениях, поэтому построение может быть описано как K строк из N символов-скобок. Назовем эти строки S1, S2, :, SK. ФД заметил, что некоторые диапазоны коров "параллельно сбалансированы". Диапазон i..j коров называется "параллельно сьалансированным" тогда и только тогда, когда строки S1,S2,:,SK сбалансированы в этом диапазоне. Например, если K=3 и у нас есть 3 строки
S1 = )()((())))(()) S2 = ()(()()()((()) S3 = )))(()()))(()) 1111 01234567890123
Тогда диапазон [3:8] параллельно сбалансирован, поскольку S1[3...8] = ((())) S2[3...8] = ()()() S3[3...8] = (()())
Диапазоны [10...13] и [11...12] также параллельно сбалансированы.
Ваша задача - посчитать количество сбалансированных диапазонов для заданных K строк длины N.
Строка S называется сбалансированной, если количество левых скобок равно количеству правых и для любого префикса этой строки количество левых скобок не меньше чем количество правых скобок.
Например эти строки сбалансированы () (()) ()(()())
А эти - нет: )( ())( ((())))
PROBLEM NAME: cbs
Формат входных данных
* Строка 1: Два целых числа, K и N.
* Строки 2..K+1: Каждая строка содержит N скобок.
Формат выходных данных
* Строка 1: Одно целое число - количество сбалансированных диапазонов
Префиксные суммы(минимумы, ...)
—Войти и решать
Typo#89844

Беси только что купила новый лэптоп. Однако ей неудобно работать с клавиатурой, поэтому она набирает строки из круглых скобок. Она может ошибиться и набрать ( вместо ) и наоборот.
Посчитайте количество мест в строке таких, что замена одной скобки на противоположную в этом месте сделает строку сбалансированной.
Есть несколько способов определить, что такое "сбалансированная" строка скобок. Например, так: 1) Всего должно быть одинаковое количество левых ( и правых ) скобок и для любого префикса этой строки, левых скобок должно быть не меньше чем правых.
Следующие строки сбалансированы () (()) ()(()())
А эти - нет:
)( ())( ((())))
PROBLEM NAME: typo
Формат входных данных
* Строка 1: строка из скобок с длиной N (1 <= N <= 100,000).
Формат выходных данных
* Line 1: количество позиций в этой строке, (если они вообще есть), таких, что замена одной скобки на противоположную в этой позиции приведет к тому, что строка станет сбалансированной.
Примечание
Для исходной строки:
12345678 ()(())))
Замена скобки в позиции 2 приводит к такой сбалансированной строке
12345678 (((())))
Аналогично сбалансированные строки получается при замене скобок в позициях 5, 6, и 7.
Префиксные суммы(минимумы, ...)
—Войти и решать
Haybale Restacking#89837

Фермер Джон заказал большое количество пакетов с сеном. Он хочет разложить их в N кучек (1 <= N <= 100,000), расположенных по кругу, где куча i содержит Bi пакетов с сеном. Водитель грузовика разложил пакеты в N куч с Ai пакетов в каждой. Известно, что сумма Bi равна сумме Ai.
ФД хочет переместить кучи из их текущего положения Ai в требуемое BI. X единиц работы требуется, чтобы переместить один пакет из кучи в другую, которая отстоит на X шагов от данной по кругу.
Определите минимальное количество работы, требуемое для преобразования "хаоса" в "порядок".

PROBLEM NAME: restack
Формат входных данных
* Строка 1: Одно целое число N.
* Строки 2..1+N: Строка i+1 содержит два целых числа Ai и Bi (1 <= Ai, Bi <= 1000).
Формат выходных данных
Примечание
Минимальное количество работы, которое надо совершить, равно 13: переместить 6 пакетов из кучи 1 в кучу 4, переместить 1 пакет из кучи 3 в кучу 2, переместить 6 пакетов из кучи 3 в кучу 4.

Префиксные суммы(минимумы, ...)
—Войти и решать
Haybale Stacking#89826

Беси согласилась помочь ФД уложить пакеты с сеном. Она начинает с N (1 <= N <= 1,000,000, N нечетное) пустых стеков, пронумерованных от 1 до N. Затем ФД дает ей последовательность из K инструкций (1 <= K <= 25,000), каждая вида A B, означающая, что Беси должна добавить по одному пакету с сеном в каждый из стеков в диапазоне от A до B. Например, инструкция 10 13 означает, что Беси должна положить по пакету сеном в стеки 10, 11, 12, 13.
После того как вся работа закончена, ФД хочет узнать медианную высоту всех N своих стеков - то есть высоту среднего стека, если все стеки упорядочить по высоте. По условию N нечетно, поэтому этот стек уникален. Пожалуйста, помогите Беси ответить на этот вопрос.
PROBLEM NAME: stacking
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N K.
* Строки 2..1+K: Каждая строка содержит одну инструкцию ФД в виде двух целых (разделенных пробелом) чисел A B (1 <= A <= B <= N).

Формат выходных данных
* Строка 1: Медианная высота после того как Беси выполнит все инструкции


Примечание
После того, как Беси закончит, стеки будут иметь высоты 0,1,2,3,3,1,0. Если их упорядочить, получим: 0,0,1,1,2,3,3. Средний элемент равен 1.

Алгоритмы обработкиИспользование сортировкиПрефиксные суммы(минимумы, ...)
—Войти и решать
Running Away From the Barn#89811

Время дойки на ферме Джона, но коровы сбежали. Ферма Джона - это множество из N (1 <= N <= 200,000) пастбищ, пронумерованных от 1 до N, и связанных N - 1 двунаправленными дорожками. Амбар расположен в пастбище 1 и любое пастбище достижимо от амбара.
Коровы бегут в сторону "от амбара" и они пробегают расстояние не больше чем L. Для каждого пастбища ФД хочет знать, в скольки различных пастбищах могут оказаться коровы, сбежавшие с этого пастбища.
Замечание: используйте 64-битные целые (int64 в Pascal, long long в C/C++ и long в Java) для хранения расстояний.
PROBLEM NAME: runaway
Формат входных данных
* Строка 1: 2 целых числа, N и L (1 <= N <= 200,000, 1 <= L <= 10^18)
* Строки 2..N: i-ая строка содержит два целых числа pi и li. pi (1 <= pi < i) - первое пастбище на кратчайшем пути между пастбищем i и амбаром li (1 <= li <= 10^12) - длина этого пути
Формат выходных данных
* Строки 1..N: По одному числу в строке. Число в строке i - количество пастбищ, которые могут быть достигнуты из пастбища i, выбирая дороги, строго удаляясь от амбара (пастбище 1) с суммарной длиной не превышающей L.
Примечание
Корова из пастбища 1 может добежать до пастбищ 1, 2, 4. Корова из пастбища 2 может добежать до пастбищ 2, 3. Пастбища 3 и 4 - конечные, оттуда некуда бежать, можно только остаться в них.
Дерево отрезков, RSQ, RMQДеревья
✓ 0✗ 1—Войти и решать
First!#89809

Беси опять играет со строками. Она обнаружила, что изменяя порядок алфавита она може добиться, чтобы некоторая строка стала лексикографически раньше всех.
Например, среди строк
"omm", "moo", "mom", "ommnom"
она может сделать первой строку "mom", используя стандартный алфавит. и она может сделать первой строку "omm" используя алфавит "abcdefghijklonmpqrstuvwxyz". Однако Беси не знает как сделать первым слово "moo" или "ommnom"
Помогите Беси вычислить строки из ввода, которые можно сделать первыми изменив порядок букв в алфавите.
Чтобы определить, что строка X лексикографически раньше cтроки Y найдите индекс первого символа в котором они различаются j. Если такого индекса нет, тогда X лексикографически меньше чем Y, если X короче чем Y, иначе, X лексикографически раньше чем Y, если X[j] находится в алфавите раньше чем Y[j].

PROBLEM NAME: first
Формат входных данных
* Строка 1: целое N (1 <= N <= 30,000),количество строк, с которыми играет Беси
* Строки 2..1+N: Каждая строка содержит не пустую строку символов. Общее количество символов во всех строках не превысит 300,000. Все символы на вводе - маленькие латинские буквы от 'a' до 'z'. Во вводе нет повторяющихся строк.

Формат выходных данных
* Строка 1: одно число K, количество строк, которые могут быть лексикографически первыми.
* Строки 2..1+K: (1+i)-ая строка должна содержать i-ую строку, которая может быть лексикографически первой. Строки нужны выводить в том же порядке, в котором они следовали на вводе.
Примечание
Только "omm" и "mom" могут стать первыми.

БорграфыТопологическая сортировка
✓ 1✗ 1—Войти и решать
Above the Median#89800
Problem 1: Above the Median [Brian Dean]
Фермер Джон выстроил N (1 <= N <= 100,000) своих коров, чтобы померять их высоты. Корова i имеет высоту Hi (1 <= Hi <= 1,000,000,000) нанометров. ФД производит очень точные измерения! ФД хочет сфотографировать некоторую непрерывную последовательность своих коров, и послать эту фотографию на соревнование.
Допускается к соревнованию только фотография группы коров, у которой медианная высота не менее чем заданная величина X (1 <= X <= 1,000,000,000).
В этой задаче мы определяем медианой массива A[0..K] значение A[ceiling(K/2)] после того, как A отсортировали. Здесь ceiling(K/2) – это округление K/2 до ближайшего целого. Например, медиана от {7, 3, 2, 6} есть 6, а медиана от {5,4,8} есть 5.
Помогите ФД посчитать количество различных непрерывных последовательностей коров, фотографии которых будут допущены к соревнованию.
PROBLEM NAME: median
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа: N и X.
* Строки 2..N+1: Строка i+1 содержит одно целое число Hi.
Формат выходных данных
* Строка 1: Количество подпоследовательностей коров ФД, у которых медиана не менее X. Заметим, что это число может не поместиться в 32-битное целое.
Примечание
Всего существует 10 непрерывных последовательностей. Однако только 7 из них имеют медиану не менее 6: {10}, {6}, {10, 5}, {5, 6}, {6, 2}, {10, 5, 6}, {10, 5, 6, 2}.
Префиксные суммы(минимумы, ...)
—Войти и решать
Списал ли Петя?#84687

Учитель математики дал двум ученикам, Пете и Васе, задания. Нужно мог ли Петя списать все заданяи у Васи, то есть является ли множество заданий Пети подмножеством заданий Васи .

Множество A является подмножеством B (A ⊆ B), если каждый элемент A также является элементом B.

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

В первой строке — число N (1 ≤ N ≤ 100000) — количество заданий Пети.

Во второй строке — N целых чисел — номера заданий Пети (1 ≤ номер ≤ 1000000).

В третьей строке — число M (1 ≤ M ≤ 100000) — количество заданий Васи.

В четвёртой строке — M целых чисел — номера заданий Васи.

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

"YES", если множество Пети является подмножеством множества Васи, иначе "NO".

Хеш
✓ 2✗ 3—Войти и решать
Минимальный и максимальный балл#84681

На шахматном турнире участники получают баллы. Судья хочет в любой момент знать: какой максимальный и какой минимальный балл среди всех участников?

Участники могут присоединяться к турниру или выбывать:

+ X — игрок с баллом X пришёл на турнир

- X — игрок с баллом X ушёл с турнира

? — запрос минимального и максимального балла

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

В первой строке — число Q (1 ≤ Q ≤ 100000) — количество событий.

В следующих Q строках — события в указанном формате.

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

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

Для каждого запроса "?" выведите два числа через пробел: минимальный и максимальный балл.

Дерево отрезков, RSQ, RMQ
—Войти и решать
Поделиться
Класснуть