Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Адаптивный поиск

(Время: 2 сек. Память: 16 Мб Сложность: 80%)

Знаменитая компания "Gold&Silver Soft" решила занять ведущее место в области разработки реляционных баз данных. Руководство компании понимает, что для этого необходимо удивить потребителей быстродействием своего программного продукта.

Ни для кого не секрет, что в основе реляционной базы данных лежит таблица, которую можно рассматривать как одномерный массив записей. Известно, что при поиске все записи таблицы просматриваются последовательно, начиная с самой первой и заканчивая найденной.

Технический отдел компании установил, что часто бывает так, что поиск одной и той же записи в таблице производится несколько раз. Основываясь на этом, программисты решили после каждого нового поискового запроса менять порядок следования записей в таблице. Другими словами, после поиска найденная запись перемещается на первое место в таблице. Очевидно, что чем чаще осуществляется поиск определенной записи, тем ближе она будет к началу таблицы и тем быстрее будет поиск этой записи.

Вашей задачей является написать программу, которая для каждого из M последовательно заданных поисковых запросов будет определять количество просмотренных записей при поиске заданной. Для простоты обозначения будем считать, что имеется таблица с N записями, где запись – это число от 1 до N. В начале все записи в таблице расположены в порядке возрастания, то есть на i-м месте в таблице находится число i. Для приведенного ниже примера при M = 2, N = 6 и запросах на поиск чисел «5» и «3» потребуется 5 и 4 просмотра записей соответственно.

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

Первая строка входного файла INPUT.TXT содержит два целых числа N и M (1 ≤ N, M ≤ 65535) — количество записей в таблице и количество запросов на поиск соответственно. Числа разделены одиночным пробелом.

Вторая строка содержит M натуральных чисел Ai (1 ≤ Ai ≤ N), разделенных одиночными пробелами, где Ai — запрос на поиск числа Ai в таблице. Запросы на поиск выполняются последовательно в порядке их ввода.

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

Единственная строка выходного файла OUTPUT.TXT должна содержать M натуральных чисел, разделенных одиночными пробелами, i-е число – это количество просмотренных записей при поиске числа Ai.

Примеры

INPUT.TXTOUTPUT.TXT
16 2
5 3
5 4
210 10
10 9 8 7 6 5 4 3 2 1
10 10 10 10 10 10 10 10 10 10
33 14
3 2 3 3 1 1 2 2 1 1 1 1 2 1
3 3 2 1 3 1 3 1 2 1 1 1 2 2

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483