ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Алгоритмы и структуры данных — 2020. Набор задач 6 > задача:


H. Евгений и Пикабу

Алгоритмы и структуры данных — 2020. Набор задач 6

Старт: 13.ноя.2020 в 08:00:00
Финиш: 27.ноя.2021 в 08:00:00
Турнир завершён!
• Турнирная таблица

Задачи турнира

• Подсказки к задачам
• A. Листья
• B. Листья: валидатор
• C. Макс и ожидание маршрутки
• D. Макс и супермаркет
• E. Макс и командировочные доку...
• F. Лучше, чем приоритетная очередь
• G. Макс и новогодние подарки
• H. Евгений и Пикабу

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Евгений и Пикабу
Евгений и Пикабу
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Если вы вдруг не знаете, Пикабу — это такой популярный сайт со смешными картинками и невероятными историями, успешно и массово убивающий время сотен тысяч людей. Евгений довольно давно не заходил на Пикабу — и, наконец, сорвался.

За время отсутствия Евгения на сайте накопилось N новых постов (мини-статей). Для удобства пронумеруем их от 1 до N.

Несмотря на впечатляющую усидчивость Евгения, даже ему могло оказаться не под силу прочитать все посты за один присест. Поэтому Евгений заходил на сайт M раз, в течение i-го из которых он читал посты с номерами от Li до Ri (возможно, некоторые из них он уже видел ранее — но разве Евгения это остановит?).

В какой-то момент Евгению стало интересно, какое общее количество различных постов он прочитал. Помогите ему ответить на этот вопрос.

А чтобы задача не показалась вам слишком простой, выводите ответ после каждого из M визитов Евгения на сайт.

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

Первая строка содержит целые числа N и M (1 ≤ N ≤ 1012, 1 ≤ M ≤ 105) — соответственно количество постов на сайте и количество визитов Евгения.

Следующие M строк описывают визиты Евгения. Каждая из них содержит целые числа Li и Ri (1 ≤ Li ≤ Ri ≤ N) — номера первого и последнего из постов, просмотренных Евгением в течение визита.

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

Выведите M целых чисел — общие количества различных постов, просмотренных Евгением после каждого захода на сайт.

Примеры

Входные данные
10 5
1 3
6 9
3 4
8 9
5 8
Выходные данные
3 7 8 8 9 
Входные данные
20 6
5 10
12 20
1 3
4 8
11 11
2 19
Выходные данные
6 15 18 19 20 20 

Для отправки решений необходимо выполнить вход.

www.contester.ru