Экзамен по истории

[22hope22]

Ребят, срочно нужна ваша помощь

1196. Экзамен по истории
Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Будем справедливы: сессия ставит задачи не только студентам, но и преподавателям. Любой преподаватель обучает немалое количество студентов, а ведь каждого надо еще и проверить. Поэтому один из преподавателей решил принимать экзамен по истории по такой упрощённой процедуре: студент записывает все известные ему «исторические» даты (достаточно, чтобы он написал только года, но, конечно, мог объяснить, чем замечательна та или иная дата). Преподаватель же держит перед глазами список дат, которые студент должен знать. Для оценки знаний студента преподаватель подсчитывает количество чисел в списке студента, которые также есть в списке преподавателя. В зависимости от полученного числа и выставляется итоговая оценка.
Вы должны оказать посильную помощь в автоматизации этого процесса, разработав программу для подсчёта количества совпадений в списках студента и преподавателя.

Исходные данные
В первой строке содержится число N — количество записей в списке преподавателя. 1 ≤ N ≤ 15000. Затем идет N строк, содержащих список преподавателя, по одной дате в строке. Записаны только года. Каждый год — целое число в пределах от 1 до 109. Даты в этом списке отсортированы по неубыванию. В следующей после списка строке содержится число M — количество записей в списке студента, 1 ≤ M ≤ 106. Затем также M строк с датами (записаны только года, каждый год — целое число в пределах от 1 до 109). Этот список не отсортирован. В списке как студента, так и преподавателя даты могут повторяться.

Результат
Вы должны вывести одно число — количество чисел во втором списке, которые также содержатся в первом.

Пример
исходные данные результат
2 2
1054
1492
4
1492
65536
1492
100

[Abstraction]

Каждый год — целое число в пределах от 1 до 109.

Дайте угадаю. Степень потерялась, да?
Ну почему Вы не можете вычитать текст перед отправкой?..

А так, гуглите "бинарный поиск". Время - O(M*lnN), память - O(N). По памяти уложитесь точно, по времени должны.