Однажды Боб проснулся и понял, что ему необходимо составить олимпиаду по информатике! Он быстро накидал несколько задач и теперь ему нужно выбрать те, которые которые он не считает тривиальными. Задача, на которую он смотрит сейчас описывается $$$3$$$ числами:
Вам нужно посчитать, сколько времени займет написание полного решения
На вход дается $$$3$$$ числа: $$$A$$$, $$$B$$$, $$$C$$$ – описание задачи ($$$0 \leq C \leq A \leq 10^9$$$, $$$0 \leq B \leq 10^9$$$)
Выведите одно число: количество часов, которые надо потратить на разработку задачи
В задаче используется оценка по группам. Баллы за группу начисляются только при прохождении всех тестов группы. Группа тестируется только если все необходимые предыдущие группы были пройдены.
| Группа | Баллы | Доп. ограничения | Зависимые группы |
| 1 | 17 | $$$A = 0$$$ | |
| 2 | 25 | $$$B = 0$$$ | |
| 3 | 28 | $$$C = 0$$$ | 1 |
| 4 | 30 | Без дополнительных ограничений | 1, 2, 3 |
211
2
В одной раздевалке есть $$$10^{18}+2$$$ шкафчиков, пронумерованных числами от $$$1$$$ до $$$10^{18}+2$$$ включительно.
Все шкафчики покрашены в два цвета: белый и синий. Они разбиты на блоки по $$$3$$$ шкафчика в каждом(из-за чего их и получилось именно $$$10^{18}+2$$$). В каждом блоке цвета идут в следующем порядке: белый, синий, белый. Другими словами, в каждом блоке:
Евлампий работает администратором раздевалки. Иногда его начальник задаёт ему вопрос: "Сколько синих шкафчиков находится на отрезке от шкафчика с номером $$$l$$$ до шкафчика с номером $$$r$$$ включительно?" Помогите Евлампию быстро отвечать на такие вопросы.
Например: Пусть начальник спрашивает про отрезок от $$$1$$$ до $$$10$$$. Выпишем первые $$$10$$$ шкафчиков по блокам:
Синими оказались шкафчики с номерами $$$2, 5, 8$$$. Всего их $$$3$$$. Значит, ответ: $$$3$$$.
Вводится два числа: $$$L$$$ и $$$R$$$ ($$$1 \le l \le r \le 10^{18}+2$$$) — запрос начальника Евлампия. Каждое число вводится в отдельной строке
Выведите единственное число — ответ на задачу
В задаче используется оценка по группам. Баллы за группу начисляются только при прохождении всех тестов группы. Группа тестируется только если все необходимые предыдущие группы были пройдены.
| Группа | Ограничения | Баллы | Зависимые группы |
| $$$0$$$ | Тесты из условия | $$$0$$$ | |
| $$$1$$$ | $$$ L = 1, 1 \le R \le 10$$$ | $$$8$$$ | $$$0$$$ |
| $$$2$$$ | $$$ L = R$$$ | $$$12$$$ | – |
| $$$3$$$ | $$$0 \le R-L \le 2 \cdot 10^{5}$$$ | $$$32$$$ | $$$1, 2$$$ |
| $$$4$$$ | Без дополнительных ограничений | $$$48$$$ | $$$0, 1, 2, 3$$$ |
111
4
91000000000000000002
333333333333333331
ХХХ — удивительные существа, обладающие двумя манипуляторами (которые очень похожи на руки), на каждом из которых по $$$k$$$ сенсорных отростков, похожих на пальцы. Для общения они используют специальный передатчик, который посылает сигналы на разных частотных каналах. Нумерация отростков следующая:
Главное галактическое приветствие ХХХ — это строго определенная последовательность из $$$2k$$$ сигналов. Чтобы передать одно приветствие, они должны последовательно активировать каналы в следующем порядке:
Полная последовательность каналов для одного приветствия: $$$1, k+1, 2, k+2, \dots, k, 2k$$$.
Кто-то записал длинный фрагмент межзвездного эфира длины $$$n$$$, содержащий множество различных сигналов. Теперь он хочет проанализировать эти данные, чтобы понять, как часто ХХХ передавали свое приветствие. Он обратился к вам, как к самому опытному аналитику данных в вашей долине. У вас есть несколько запросов: для каждого временного промежутка от $$$l$$$ до $$$r$$$ вы хотите узнать, сколько существует подотрезков на заданном отрезке, таких, что они являются последовательностью приветствия.
Комбинация считается полностью переданной в промежутке $$$[l, r]$$$, если моменты времени всех $$$2k$$$ её сигналов принадлежат этому промежутку.
Первая строка содержит три целых числа $$$n$$$, $$$k$$$, $$$q$$$ $$$(1 \le n,\ k,\ q \le 2 \cdot 10^5)$$$ — длина записанной последовательности сигналов, количество сенсорных отростков на одном манипуляторе и количество ваших запросов.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2\cdot k$$$) — последовательность номеров каналов, записанная на фрагменте эфира.
Следующие $$$q$$$ строк содержат запросы. Каждая строка содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) — временной промежуток, для которого нужно найти количество полных приветствий.
Для каждого запроса выведите одно целое число в новой строке — количество раз, которое приветствие было полностью передано в промежутке с $$$l$$$-й по $$$r$$$-ю позицию включительно.
В задаче используется оценка по группам. Баллы за группу начисляются только при прохождении всех тестов группы. Группа тестируется только если все необходимые предыдущие группы были пройдены.
| Подзадача | Доп. ограничения | Баллы | Зависимые группы |
| $$$1$$$ | $$$n,k,q \le 100$$$ | $$$11$$$ | — |
| $$$2$$$ | $$$n,k,q \le 1000$$$ | $$$25$$$ | $$$1$$$ |
| $$$3$$$ | $$$k \le 100, n,q \le 2\cdot 10^{5}$$$ | $$$17$$$ | $$$1$$$ |
| $$$4$$$ | $$$k = 1$$$ | $$$9$$$ | — |
| $$$5$$$ | Для всех $$$i$$$ $$$ a_{i}=1$$$ | $$$7$$$ | — |
| $$$6$$$ | $$$ r-l \le 10 $$$ | $$$12$$$ | — |
| $$$7$$$ | Без дополнительных ограничений | $$$19$$$ | $$$1,2,3,4,5,6$$$ |
5 1 31 2 1 2 15 52 44 5
0 1 0
6 2 31 3 1 3 2 41 63 62 4
1 1 0