Мастер-класс 2018. Весна. RMQ

Problem A. Longest Ordered Subsequence ≡

problems
details
visible spaces
basic formulae
wide text
editor

Author:	Far-Eastern Subregional	Time limit:	1 sec
Input file:	input.txt	Memory limit:	8 Mb
Output file:	output.txt

Statement

A numeric sequence of a_i is ordered if a₁ < a₂ < ... < a_N. Let the subsequence of the given numeric sequence (a₁, a₂, ., a_N) be any sequence (a_i1, a_i2, ., a_iK), where 1 ≤ i₁ < i₂ < ... < i_K ≤ N. For example, the sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences of this sequence are of length 4, e. g., (1, 3, 5, 8).

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

Input file format

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces.

Output file format

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

Constraints

1 ≤ N ≤ 1000

Sample tests

No.	Input file (`input.txt`)	Output file (`output.txt`)
1	`7 1 7 3 5 9 4 8`	`4`

Задача B. Наибольшая возрастающая подпоследовательность ≡

задачи
детали
видимые пробелы
простые формулы
широкий текст
редактор

Входной файл:	input.txt		Ограничение времени:	2 сек
Выходной файл:	output.txt		Ограничение памяти:	64 Мб

Условие

Дана последовательность из N целых чисел. Найдите любую из ее наибольших строго возрастающих подпоследовательностей.

Формат входного файла

Во входном файле находится число N, а за ним следует последовательность a_i из N целых чисел.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 100000; −10⁹ ≤ a_i ≤ 10⁹

Примеры тестов

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`5 123 456 124 124 125`	`3 1 4 5`

Задача C. Выборы заведующего кафедрой ≡

задачи
детали
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	Г. Гренкин, И. Туфанов	Ограничение времени:	2 сек
Входной файл:	input.txt	Ограничение памяти:	256 Мб
Выходной файл:	output.txt

Условие

В ДВФУ произошло укрупнение кафедры информатики. В связи с этим встал вопрос выборе нового заведующего кафедрой. На кафедре работает много преподавателей и непросто выбрать самого достойного. Посовещавшись, преподаватели занумеровали себя и для преподавателя с номером i определили следующие числа:

m_i — уровень познаний в математике;
p_i — уровень познаний в программировании;
t_i — преподавательское мастерство;

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

Считается, что, i-й преподаватель является кандидатом на должность заведующего кафедрой в том и только том случае, когда для него не найдётся такого j-того преподавателя, что одновременно m_j > m_i, p_j > p_i, t_j > t_i.

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

Формат входного файла

Входной файл содержит натуральное число n — количество преподавателей. Далее следует n троек натуральных чисел m_i p_i t_i.

Формат выходного файла

Требуется вывести в выходной файл номера отобранных преподавателей в порядке возрастания.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ m_i, p_i, t_i ≤ 10⁹

Примеры тестов

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`4 2 3 4 1 1 3 2 1 8 3 2 10`	`1 4`