4-й этап Республиканской олимпиады по информатике 2019, 9 класс, Актобе
Задача C. Поиск медианы
Ограничение по времени:
3 секунды
Ограничение по памяти:
512 мегабайт
Дан массив чисел a длинны n и q запросов. Каждый из запросов описывается числами l и r. Для каждого из запросов нужно найти, какой будет медиана в массиве, если удалить числа из массива от l до r.
Формат входного файла
В первой строке входных данных подаются 2 числа n,q (1<=n,q<=106) — количество чисел в массиве и количество запросов.
Во второй строке входных данных подаются n целых чисел ai (1<=ai<=109) — i-й элемент массива a.
В последующих q строках подаются по два целых числа l,r (1<=l<=r<=n) — границы удаляемого отрезка. Гарантируется что в оставшемся массиве будет хотя бы один элемент.
Формат выходного файла
Для каждого запроса выведите ответ в отдельной строке, медиана оставшегося массива.
Система оценки
Данная задача содержит шесть подзадач:
- 1<=n<=1000,1<=q<=1000,1<=ai<=109. Оценивается в 8 баллов.
- 1<=n<=100000,1<=q<=100000,1<=ai<=ai+1<=109. Оценивается в 9 баллов.
- 1<=n<=100000,1<=q<=10000,1<=ai<=109. Оценивается в 19 баллов.
- 1<=n<=100000,1<=q<=100000,1<=ai<=100. Оценивается в 15 баллов.
- 1<=n<=100000,1<=q<=100000,1<=ai<=109. Оценивается в 31 баллов.
- 1<=n<=500000,1<=q<=1000000,1<=ai<=109. Оценивается в 18 баллов.
Пример:
Вход 5 5 1 2 1 4 9 2 4 1 1 4 5 3 4 1 3Ответ
1 2 1 2 4
Замечание
Медианой массива длинны n называется элемент который стоит на позиции n+12 в отсортированном виде.
В первом примере, после проведения первой операции, удалится отрезок [2,1,4] и останется [1,9]. Так как длинна оставшегося массива равна 2, позиция на которой попадает медиана равна 32=1.
После проведения второй операции, удалится отрезок [1] и останется [2,1,4,9]. Так как длинна оставшегося массива равна 4, позиция на которой попадает медиана равна 52=2. Вторым элементом в отсортированном оставшемся массиве будет 2.
После проведения третьей операции, удалится отрезок [4,9] и останется [1,2,1]. Так как длинна оставшегося массива равна 3, позиция на которой попадает медиана равна 42=2. Вторым элементом в отсортированном оставшемся массиве будет 1.
(
Nurdaulet Akhanov
)
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.