Задача A. Контейнеры и отсеки

Вы главный разработчик в компании грузоперевозок Нурлаш и КО inc. Компании требуется, чтобы вы написали новый функционал для сортирующего робота. Робот контролирует $N$ отсеков, последовательно пронумерованных от 1 до $N$, и может выполнять два типа операций:

• Добавить контейнер с номером $C$ в каждый отсек с $L$-го по $R$-ый
• Убрать последний контейнер из каждого отсека с $L$-го по $R$-ый

Номер контейнера — целое положительное число не превышающее $10^9$.
Вам даны операции в том порядке в котором их выполнял робот. Требуется определить, для каждого отсека, контейнер с каким номером является последним в нем после выполнения всех операций.

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

Первая строка входных данных содержит два числа — $N$, $M$ ($1 \leq N, M \leq 10^5$), количество отсеков и количество операций соответственно.
Далее в $M$ строках содержится по три числа $L$, $R$ и $C$ ($1 \leq L \leq R \leq 10^5$, $0 \leq C \leq 10^9$), описание операций. Если $C = 0$, то это операция второго типа, иначе — первого.

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

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

Выведите в единственной строке $N$ чисел, разделенных пробелом. Первое число — номер последнего контейнера в первом отсеке, второе - во втором, и т.д. Если отсек пуст, выведите $0$.

Примеры:

Вход:

5 3
1 5 1
2 4 0
4 5 10

Ответ:

1 0 0 10 10

Оценивание:

Данная задача содержит две подзадачи:

• $1 \leq N, M \leq 1000$. Подзадача оценивается в $40$ баллов.
• $1 \leq N, M \leq 10^5$. Подзадача оценивается в $60$ баллов.

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

Задача B. Кафе

Сегодня в кафе Нового Университета (НУ) пришли $N$ студентов. Каждый из них хочет выпить чашку кофе и съесть одно пирожное (никто из них не согласен только на кофе либо только на пирожное — в этом случае студент уходит). В кафе подают $M$ видов кофе и $K$ видов пирожных. Для каждого из видов кофе или пирожного известно, сколько чашек или порций этого вида имеется в наличии.

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

Хозяин кафе задумался: какое максимальное количество студентов он сможет обслужить? А вы можете посчитать это число?

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

Первая строка входных данных содержит целые числа $N$, $M$, $K$ ($1 \le N, M, K \le 500$).
Во второй строке записано $M$ целых чисел через пробел $C_1,C_2,\dots,C_M$ ($1 \le C_i \le 500$) — количество чашек кофе каждого вида, имеющихся в наличии.
В третьей строке записано $K$ целых чисел через пробел $P_1,P_2,\dots,P_K$ ($1 \le P_i \le 500$) — количество порций пирожных каждого вида, имеющихся в наличии.
В следующих $N$ строках дана информация о том, какие виды кофе любит каждый студент. $i$-я строка ($1 \le i \le N$) содержит число $X_i$, за которым следуют различные числа $A_1,A_2,\dots,A_{X_i}$ — виды кофе, которые любит $i$-й студент.
Следующие $N$ строк задают информацию о том, какие виды пирожных любит каждый студент. $i$-я строка ($1 \le i \le N$) содержит число $Y_i$, за которым следуют различные числа $B_1,B_2,\dots,B_{Y_i}$ — виды пирожных, которые любит $i$-й студент.

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

Выведите единственное число — ответ на задачу.

Примеры:

1.Вход:

2 3 1 
5 1 3 
2
3 1 2 3 
1 2
1 1
1 1

Ответ:

2

Оценивание:

Данная задача содержит 3 подзадачи:
$1 \le N, M, K \le 5$. Сумма всех $X_i$ и $Y_i$ ($1 \le i \le N$) вместе не превосходит $10$. Оценивается в $21$ балл.
$1 \le N, M, K \le 20$. Сумма всех $X_i$ и $Y_i$ ($1 \le i \le N$) вместе не превосходит $15$. Оценивается в $33$ балла.
$1 \le N, M, K \le 500$. Сумма всех $X_i$ и $Y_i$ ($1 \le i \le N$) вместе не превосходит $2000$. Оценивается в $46$ баллов.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих.

Задача C. Temirulan vs Pernekhan

Темирулану и Пернехану подарили последовательность $A$ из $1 \le N \le 5000$ целых положительных чисел. Они договорились поделить эту последовательность. Каждый из них должен взять некоторую не пустую последовательную часть последовательности, причем часть Темирулана должна начинаться раньше части Пернехана. Они хотят выглядеть уникально, поэтому они хотят чтобы не существовало ни одного числа, встречающегося в участке Темирулана и Пернехана одновременно. Айдос, наблюдавший за ними, заинтересовался, сколько существует различных способов сделать это. Помогите ему, напишите программу для количества способов.

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

Первая строка входных данных содержит целое число $N$. Следующая строка содержит $N$ целых чисел $1 \le A_i \le N$, $1 \le i \le N$, разделенных пробелами.

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

Выведите единственное число — ответ на задачу.

Примеры:

1.Вход:

3
1 2 3 

Ответ:

5

2.Вход:

4
1 2 3 2

Ответ:

9

3.Вход:

1
1

Ответ:

0

Во втором тестовом примере есть следующие способы разделения:
{ [1] [2] 3 2 }, { [1] [2 3] 2}, { [1] [2 3 2] },
{ [1] 2 [3] 2 }, { [1] 2 [3 2] }, { [1] 2 3 [2] },
{ [1 2] [3] 2 }, { 1 [2] [3] 2 }, { 1 2 [3] [2] }

Оценивание:

Данная задача содержит четыре подзадачи:
$1 \le N \le 50$. Оценивается в $11$ баллов.
$1 \le N \le 500$. Оценивается в $21$ балл.
$1 \le N \le 2000$. Оценивается в $31$ балл.
$1 \le N \le 5000$. Оценивается в $37$ баллов.

Задача D. Arti vs Mex-Mans

У Артема была последовательность $x$ из $1 \le N \le 100$ чисел, для которой выполнялось следующее свойство $1 \le L \le x_1 \le x_2 \le \ldots \le x_N \le R \le 10^9$, а наименьшее общее кратное этих чисел делилось на $1 \le A \le 10^9$. Но пришел Мансур и украл последовательность $x$. Артем очень расстроился, ведь он не помнит значения чисел своей последовательности. Он помнит только числа $N$, $L$, $R$ и $A$. Он хочет восстановить последовательность. Для этого он решил сначала посчитать, а сколько вообще существует последовательностей, с такими же $N$, $L$, $R$ и $A$. Помогите ему, — напишите программу для решения этой задачи.

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

Единственная строка входных данных содержит четыре целых положительных числа, разделенных пробелами: $N$, $L$, $R$, $A$.

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

Выведите единственное число, ответ на задачу. Так как ответ может быть очень большим, выведите его остаток от деления на $10^9 + 7$.

Примеры:

1.Вход:

2 1 7 6 

Ответ:

9

2.Вход:

1 1 50 7

Ответ:

7

В первом тестовом примере подходящими последовательностями будут следующие::
${ 1, 6}$, ${ 2, 3}$, ${ 2, 6}$
${ 3, 4}$, ${ 3, 6}$, ${ 4, 6}$
${ 5, 6}$, ${ 6, 6}$, ${ 6, 7}$

Оценивание:

Данная задача содержит 5 подзадачи:
$1 \le N \le 2$, $1 \le A,L,R \le 100$. Оценивается в $6$ баллов.
$1 \le N \le 2$, $1 \le A,L,R \le 1000$. Оценивается в $11$ баллов.
$1 \le N \le 10$, $1 \le A,L,R \le 1000$. Оценивается в $15$ баллов.
$1 \le N \le 10$, $1 \le A,L,R \le 10^6$. Оценивается в $21$ балл.
$1 \le N \le 100$, $1 \le A,L,R \le 10^9$. Оценивается в $47$ баллов.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих.

Задача E. Наурыз Cup 2015

Скоро состоится командное соревнование <<Наурыз Cup 2015>>. Команда должна состоять ровно из двух участников. Аманчик сильно хочет в нем участвовать. Он достал список всех $2 \cdot N$ ($1 \le N \le 10^5$) участников включая себя. У каждого участника есть свой рейтинг. Рейтинг команды это средний рейтинг двух участников. Чем выше рейтинг команды тем выше его место. Команда занимает место под номером $K+1$, если есть ровно $K$ команд, рейтинг которых строго больше.

Из всевозможных разбиений, какое самое высокое и самое низкое место может занять команда Аманчика. Аманчик участник под номером 1.

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

Первая строка входных данных содержит целое число $N$. Следующая строка содержит $2 \cdot N$ целых чисел $1 \le a_i \le 10^5$, $1 \le i \le 2 \cdot N$, разделенных пробелами.

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

Выведите два числа самое высокое и самое низкое место.

Примеры:

1.Вход:

3
999 3 1 2 1000 1

Ответ:

1 2

2.Вход:

1
1540 1433

Ответ:

1 1

3.Вход:

3
100000 100000 100000 100000 100000 100000

Ответ:

1 1

В первом примере если мы разобьем участников следующим образом (999, 2) (3, 1) (1000, 1) то команда Аманчика (999, 2) и команда (1000, 1) возьмут первые места, а команда (3, 1) возьмет третье место. А если мы разобьем следующим образом (999, 1) (1000, 2) (3, 1) то команда Аманчика возьмет второе место. Из всевозможных разбиений, указанные выше будут соответствовать самым высоким и самым низким местам.

Оценивание:

Данная задача содержит четыре подзадачи:
$1 \le N \le 3$. Оценивается в $7$ баллов.
$1 \le N \le 6$. Оценивается в $19$ баллов.
$1 \le N \le 2500$. Оценивается в $31$ балл.
$1 \le N \le 10^5$. Оценивается в $43$ балла.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих.