Processing math: 100%

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. 1<=n<=1000,1<=q<=1000,1<=ai<=109. Оценивается в 8 баллов.
  2. 1<=n<=100000,1<=q<=100000,1<=ai<=ai+1<=109. Оценивается в 9 баллов.
  3. 1<=n<=100000,1<=q<=10000,1<=ai<=109. Оценивается в 19 баллов.
  4. 1<=n<=100000,1<=q<=100000,1<=ai<=100. Оценивается в 15 баллов.
  5. 1<=n<=100000,1<=q<=100000,1<=ai<=109. Оценивается в 31 баллов.
  6. 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 )
посмотреть в олимпиаде

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

  1
4 года 10 месяца назад #

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

C++