Задача 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. Буквы

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

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

В первой строке входного файла задается одна строка $S$, состоящая из строчных букв английского алфавита. Во второй строке задается одно целое положительное число $K$ ($ 1\le K \le 26$).

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

Выведите ответ к задаче или -1, если такой подстроки не существует.

Примеры

aaabbccc
3

Ответ:

4

Оценивание:

Данная задача содержит три подзадачи:
длина строки $S \le 100$. Оценивается в $20$ баллов.
длина строки $S \le 5000$. Оценивается в $30$ баллов.
длина строки $S \le 10^5$. Оценивается в $50$ баллов.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих.

Задача 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. Помощь Жандосу

На прошлой неделе на уроке математики Жандос узнал как взять число по модулю. Определим A по модулю B как остаток от деления A на B и обозначим его как A mod B. Учитель по математике задал домашнее задание: найти количество чисел В от L до R включительно, что A mod B = C.

Жандосу нужно сделать домашнюю работу, но он хочет посмотреть футбол. Потому он обратился к вам за помощью. Напишите программу, которая по числам A, C, L, R найдет количество чисел B от L до R включительно, что A mod B = C.

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

В единственной строке ввода даны целые числа A, C, L, R ($0 \le A, C, L, R \le 10^9$).

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

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

Примеры:

1.Вход:

21 5 1 21

Ответ:

2

2.Вход:

32443 463 457 3716

Ответ:

12

Оценивание:

Баллы выдаются пропорционально количеству пройденных тестов.:
Не менее 25% тестов с ограничениями $0 \le R - L \le 10^6$.

Задача 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$ балла.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих.