Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2040. Светопредставление
Дерево отрезков, декартово дерево, √-декомпозицияОлимпиадные задачи на русском языке
| 19/04/2014 | Южно-Уральский открытый командный чемпионат по программированию (J) |
| 18/07/2016 | Лето 2016 - 10 (командная) (F) |
| 03/07/2020 | Летние сборы - 3 (командное) (G) |
| 19/03/2024 | Дерево отрезков (начало) (проводит BOGAT) (B) |
Ограничения: время – 1500ms/3000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Мебибайту необходимо рассчитать энергетические нагрузки во время светомузыкального шоу.
Управление `2^20` лампочками происходит следующим образом. Для каждого такта музыкального сопровождения
указаны два целых числа, определяющих диапазон номеров лампочек, состояние которых должно
измениться на противоположное. Если лампочка была выключена, она должна загореться, а
горящая лампочка — погаснуть. В начальный момент времени все лампочки выключены.
Напишите программу, определяющую количество горящих лампочек после выполнения каждой команды.
Формат ввода
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 100 000`) – количество команд на переключение
состояния лампочек. Далее следует `N` строк, каждая строка содержит два целых
числа `a_i` и `b_i` (`1\ ≤\ a_i\ ≤\ b_i\ ≤\ 2^20`) — команда на переключение.
Формат вывода
Вывести `N` строк, в `i`-ой строке вывести количество горящих лампочек после `i`-ой команды.
Пример ввода
3 5 10 3 8 1 12
Пример вывода
6 4 8
