Областная олимпиада по информатике, 2018 год, 10-11 класс


(Тима и Рама) На доске в ряд написано $N$ целых чисел. Темірлан и Рамазан играют в следующую игру:

Пока Темірлан отошел, Рамазан хочет стереть ровна $K$ чисел. Он может стереть любые числа. Когда Темірлан вернется, они начнут играть как обычно, но на доске будет написано $N-K$ чисел.
Для каждого из $Q$ чисел $K_1,K_2, ..., K_Q$, Рамазан хочет узнать, какое значение у последнего оставшегося числа, если он заранее сотрет $K_i$ чисел, и оба игрока играют оптимально?
Формат входных данных:
В первой строке находится одно целое число $N$.
Во второй строке находятся $N$ целых числа $A_1,A_2,...,A_N (1 \le A_i \le 10^6)$ --- числа написанные на доске.
В третьей строке находится одно целое число $Q$.
В четвертой строке находятся $Q$ целых числа $K_1,K_2,...,K_Q(0 \le K_i \le N - 1)$.
Формат выходных данных:
Выведите через пробел $Q$ чисел, $i$-е из них, значения последнего оставшегося числа, если Рамазан заранее сотрет $K_i$ чисел.
Примеры:
1.Вход:
4
1 4 2 3
4
0 1 2 3
Ответ:
1 3 3 4
2.Вход:
3
5 5 5
3
0 1 2
Ответ:
5 5 5
3.Вход:
6
2 7 5 4 8 10
3
3 5 2
Ответ:
7 10 7
Замечание:
В первом тесте при $K=3$, Рамазану выгодно стереть первое,второе и четвертое числа.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:
( Temirlan Satylkhanov )
посмотреть в олимпиаде

Комментарий/решение:

пред. Правка 2   -1
2018-12-13 12:19:14.0 #

  -2
2018-12-20 22:38:18.0 #

  0
2020-06-07 16:00:51.0 #

  -3
2019-01-01 16:58:56.0 #

Когда именно выдается вердикт Check Failed?

  -2
2020-01-02 14:28:20.0 #

показать/скрыть код

Работает на претестах но говорит "ошибка проверки" что это значит?

  1
2020-01-02 18:30:17.0 #

исправлена ошибка в проверяющей системе. попробуйте переотправить.

  -2
2020-01-02 18:34:01.0 #

Заработала спасибо!

  -1
2020-01-03 19:35:44.0 #

можно разбор

  0
2020-06-07 15:58:27.0 #

А как проверить решение? В этой задаче нельзя же проверить.

  -1
2020-01-03 19:25:41.0 #

админ можно разбор этой задачи

  0
2020-01-03 20:32:11.0 #

Можно доказать, если есть последовательность $a_1, a_2, ..., a_n$ то в конце останется число $min(a_1,a_n)$

Для того что бы получить число С мы должны на префиксе жадно удалить все числа меньше С и на суффиксе тоже. Если удалили $len$ чисел то $ans[len] >= C$.

показать/скрыть код

пред. Правка 2   -1
2020-01-03 21:33:11.0 #

скажите пожалуйста 10 тест

  0
2020-01-03 21:39:08.0 #

Почему ваше решение не ловит TLE, если асимптотика O($n * max(a_i)$)

  0
2020-01-03 23:01:35.0 #

Асимптотика $O(n + max(a_i))$.

Главное построить массивы prefix и suffix "проходом слева направо"

10й тест огромный.