Parassat Kyzyrkanov

Задача №1.

Задача C. Запросы на перестановке

Ограничение по времени:

1.5 секунд

Ограничение по памяти:

256 мегабайт

У вас есть перестановка $p_1, \ldots, p_n$ и массив целых чисел $a_1, \ldots, a_n$, который изначально заполнен нулями. Вам нужно обработать $q$ запросов одного из трёх типов:

$1 l r x$: для всех $l <= i <= r$, добавить $x$ к $a_{p_i}$.
$2 l r$: вычислить и вывести $a_l + a_{l+1} + \cdots + a_r$.
$3 a b$: поменять местами $p_a$ и $p_b$.

Формат входного файла

В первой строке записаны два целых числа $n$ и $q$ ($2 <= n, q <= 10^5$) — размер перестановки и количество запросов. Во второй строке записаны $n$ целых чисел $p_1, \ldots, p_n$ ($1 <= p_i <= n$, $p_i \neq p_j$ если $i \neq j$). Каждая из следующих $q$ строк содержат описания запросов Каждый запрос задан в одном из следующих форматов в зависимости от типа запроса: $1 l r x$ ($1 <= l <= r <= n$, $1 <= x <= 10^5$) для запросов первого типа. $2 l r$ ($1 <= l <= r <= n$) для запросов второго типа. $3 a b$ ($1 <= a, b <= n$, $a \neq b$) для запросов третьего типа.

Формат выходного файла

Выведите ответы на все запросы второго типа, каждый ответ в отдельной строке.

Пример:

Вход

6 9
4 6 3 1 2 5
1 4 5 3
3 3 5
1 2 3 6
3 3 6
3 2 1
2 1 5
2 1 6
1 1 5 6
2 4 6

Ответ

12
18
24

( Parassat Kyzyrkanov )
комментарий/решение(2) олимпиада

Задача №2.

Задача B. Сумма, произведение и четыре числа

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Вам даны два целых числа $s$ и $p$. Найдите количество целых положительных четверок, что их сумма не превышает $s$, а произведение не превышает $p$. Формально, в этой задаче вам нужно найти количество таких целых положительных четверок $a, b, c, d$ что выполняются два условия: 1. $a + b + c + d <= s$ 2. $a * b * c * d <= p$

Формат входного файла

В первой строке входных данных даны два целых числа $s$ и $p(1 <= s <= 500, 1 <= p <= 10^9)$.

Формат выходного файла

В единственной строке выведите ответ на задачу.

Система оценки

В этой задаче 10 тестов, каждая из них оценивается в 10 баллов:

Тесты 1-2: Примеры из условия.
Тесты 3-6: $s <= 100$.
Тесты 7-10: без дополнительных ограничений.

Примеры:

Вход

5 10

Ответ

Вход

10 15

Ответ

Замечание

Все подходящие четверки в первом примере: ($1,1,1,1$), ($2,1,1,1$), ($1,2,1,1$), ($1,1,2,1$), ($1,1,1,2$). ( Parassat Kyzyrkanov )
комментарий/решение(5) олимпиада