Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Важным элементом повышения эффективности работы сотрудников является борьба с рутиной. Построим математическую модель разнообразия типов заданий, выполняемых сотрудником в компании.
Рассмотрим работу сотрудника в течение n последовательных рабочих дней. Будем считать, что каждый день сотрудник выполняет ровно один тип заданий, обозначим тип заданий, выполняемый сотрудником в i-й день, целым числом ai.
Для оценки рутинности работы сотрудника будем использовать следующую характеристику.
Зафиксируем целое число d и рассмотрим все отрезки из d подряд идущих рабочих дней.
Для каждого такого отрезка найдём количество различных типов заданий,
которые работник выполнял на протяжении этих дней, и просуммируем эти значения.
Полученную величину обозначим как Sd и будем называть её d-разнообразием.
Чем d-разнообразие выше, тем больше различных типов заданий выполнял
сотрудник. Профилем вариативности
сотрудника будем называть массив
значений [S1,S2,…,Sn].
Требуется написать программу, которая по заданной последовательности a1,a2,…,an типов выполняемых сотрудником заданий вычисляет его профиль вариативности.
В первой строке находится единственное целое число n — количество последовательных рабочих дней, которые необходимо проанализировать (1≤n≤2⋅105).
Во второй строке находится n целых чисел a1,a2,…,an — типы заданий, которое выполнял сотрудник (1≤ai≤109).
Выведите n целых чисел: S1,S2,…,Sn.
1≤ai≤109
1≤n≤2⋅105
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
---|---|---|---|---|
1 | 12 | 1≤n≤50, 1≤ai≤50 | первая ошибка | |
2 | 10 | 1≤n≤50, 1≤ai≤109 | 1 | первая ошибка |
3 | 10 | 1≤n≤500, 1≤ai≤109 | 1,2 | первая ошибка |
4 | 12 | 1≤n≤5000, 1≤ai≤5000 | 1 | первая ошибка |
5 | 10 | 1≤n≤5000, 1≤ai≤109 | 1 - 4 | первая ошибка |
6 | 16 | 1≤n≤2⋅105, 1≤ai≤50 | 1 | первая ошибка |
7 | 30 | 1≤n≤2⋅105, 1≤ai≤109 | 1 - 6 | первая ошибка |
Рассмотрим, как вычисляются значения Sd в первом примере.
1-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из одного дня.
Отрезок дней | Типы заданий | Количество различных |
---|---|---|
1 - 1 | 1 | 1 |
2 - 2 | 3 | 1 |
3 - 3 | 2 | 1 |
4 - 4 | 1 | 1 |
5 - 5 | 2 | 1 |
Значение 1-разнообразия равно S1=1+1+1+1+1=5.
2-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из двух дней.
Отрезок дней | Типы заданий | Количество различных |
---|---|---|
1 - 2 | 1, 3 | 2 |
2 - 3 | 3, 2 | 2 |
3 - 4 | 2, 1 | 2 |
4 - 4 | 1, 2 | 2 |
Значение 2-разнообразия равно S2=2+2+2+2=8.
3-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из трех дней.
Отрезок дней | Типы заданий | Количество различных |
---|---|---|
1 - 3 | 1, 3, 2 | 3 |
2 - 4 | 3, 2, 1 | 3 |
3 - 5 | 2, 1, 2 | 2 |
Значение 3-разнообразия равно S3=3+3+2=8.
4-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из четырех дней.
Отрезок дней | Типы заданий | Количество различных |
---|---|---|
1 - 4 | 1, 3, 2, 1 | 3 |
2 - 5 | 3, 2, 1, 2 | 3 |
Значение 4-разнообразия равно S4=3+3=6.
5-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из пяти дней.
Отрезок дней | Типы заданий | Количество различных |
---|---|---|
1 - 5 | 1, 3, 2, 1, 2 | 3 |
Значение 5-разнообразия равно S5=3.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|