Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1772. Операционные системы
Сканирование, метод двух указателейДеревья (map, set), хэш-таблицы
Олимпиадные задачи на русском языке
| 25/06/2012 | Лето 2012 - дорешивание ( 6G) |
| 04/07/2012 | Лето 2012 - 6 (G) |
| 15/05/2022 | Структуры данных - множества, словари (проводит BOGAT) (D) |
| 11/11/2023 | Марафон 80 задач, 4 этап (I) |
| 02/12/2023 | Множества, словари (бонус) (проводит BOGAT) (D) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Васин жесткий диск состоит из `M` секторов. Вася последовательно устанавливал на него
различные операционные системы следующим методом: он создавал новый раздел
диска из последовательных секторов, начиная с сектора номер `a_i` и до сектора `b_i` включительно, и
устанавливал на него очередную систему. При этом если очередной раздел хотя
бы по одному сектору пересекается с каким-то ранее созданным разделом, то ранее
созданный раздел «затирается», и операционная система, которая на него была
установлена, больше не может быть загружена.
Напишите программу, которая по информации о том, какие разделы на диске создавал Вася,
определит, сколько в итоге работающих операционных систем
установлено и в настоящий момент работает на Васином компьютере.
Сначала вводятся натуральное число `M` — количество секторов на жестком диске (`1\ ≤\ M\ ≤\ 10^9`) и
целое число `N` — количество разделов, которое последовательно создавал Вася (`0\ ≤\ N\ ≤\ 100\ 000`).
Далее идут `N` пар чисел `a_i` и `b_i`, задающих номера начального и конечного секторов раздела (`1\ ≤\ \ a_i\ \ ≤\ b_i\ ≤\ M`).
Выведите одно число — количество работающих операционных систем на Васином компьютере.
Пример ввода 1
10 3 1 3 4 7 3 4
Пример вывода 1
1
Пример ввода 2
10 4 1 3 4 5 7 8 4 6
Пример вывода 2
3
Источник: Московская командная олимпиада школьников по программированию, 2009/10 учебный год
