Ограничение по времени на тест: 1 секунда
Ограничение по памяти на тест: 512 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Вам нужно научиться отвечать на запрос «сумма чисел на отрезке».
Массив не меняется. Запросов много. Отвечать на каждый запрос следует за O(1).
Размер массива — n и числа x, y, a0 , порождающие массив a: ai= (x * a{i-1} + y) mod 2^16 Далее следует количество запросовmи числа z, t, b0, порождающие массив b: bi = (z * {_bi-1} + t) mod 2^30.
Массив c строится следующим образом: ci =bi mod n. Запросы: i-й из них — найти сумму на отрезке от min(c2i; c2{i+1}) до max(c2i; c2{i+1}) в массиве a. Ограничения: 1 ⩽ n ⩽ 10^7 , 0 ⩽ m ⩽ 10^7. Все числа целые от 0 до 2^16. t может быть равно -1.
Выведите сумму всех сумм.
Входные данные
3 1 2 3
3 1 -1 4
Выходные данные
23
a = {3, 5, 7}, b = {4, 3, 2, 1, 0, 2^30 - 1}, c = {1, 0, 2, 1, 0, 0}, запросы = {[0;1], [1;2], [0;0]}, суммы = {8, 12, 3}.
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Дан массив из n чисел. Требуется написать программу, которая будет отвечать на запросы следующего вида: найти минимум на отрезке между u и v включительно.
В первой строке заданы три натуральных числа n, m ( 1 ⩽ n ⩽ 10^5 , 1 ⩽ m ⩽ 10^7 ) и a1 ( 0 ⩽ a1 < 16 714 589) — количество элементов в массиве, количество запросов и первый элемент массива соответственно. Вторая строка содержит два натуральных числа u1 и v1 ( 1 ⩽ u1 ; v1 ⩽ n) — первый запрос.
Для того, чтобы размер ввода был небольшой, массив и запросы генерируются.
Элементы a2, a3,..., an задаются следующей формулой:
ai+1 = (23 * ai + 21563) mod 16714589.
Например, при n = 10, a1 = 12345 получается следующий массив: a = ( 12345, 305498, 7048017, 11694653, 1565158, 2591019, 9471233 , 570265, 13137658, 1325095).
Запросы генерируются следующим образом:
ui+1 = ((17 * ui + 751 + ri + 2i) mod n) + 1,
vi+1 = ((13 * vi + 593 + ri + 5i) mod n) + 1,
где ri — ответ на запрос номер i.
Обратите внимание, что ui может быть больше, чем vi.
В выходной файл выведите um, vm и rm (последний запрос и ответ на него).
Входные данные
10 8 12345
3 9
Выходные данные
5 3 1565158
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
В первой строке находится число n — размер массива. ( 1 ⩽ n ⩽ 500,000) Во второй строке находится n чисел ai — элементы массива. Далее содержится описание операций, их количество не превышает 1,000,000. В каждой строке находится одна из следующих операций:
-
set i x — установить a[i] в x.
-
sum i j — вывести значение суммы элементов в массиве на отрезке сi по j, гарантируется, что ( 1 ⩽ i ⩽ j ⩽ n).
Все числа во входном файле и результаты выполнения всех операций не превышают по модулю 10^18.
Выведите последовательно результат выполнения всех операций sum. Следуйте формату выход- ного файла из примера.
Входные данные
5
1 2 3 4 5
sum 2 5
sum 1 5
sum 1 4
sum 2 4
set 1 10
set 2 3
set 5 2
sum 2 5
sum 1 5
sum 1 4
sum 2 4
Выходные данные
14
15
10
9
12
22
20
10Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
В первой строке находится число n — размер массива. ( 1 ⩽ n ⩽ 10^5 ) Во второй строке находится n чисел ai — элементы массива. Далее содержится описание операций, их количество не превышает 2 * 10^5. В каждой строке находится одна из следующих операций:
-
set i j x — установить все a[k], i ⩽ k ⩽ j в x.
-
add i j x — увеличить все a[k], i ⩽ k ⩽ j на x.
-
min i j — вывести значение минимального элемента в массиве на отрезке сi по j, гарантируется, что ( 1 ⩽ i ⩽ j ⩽ n).
Все числа во входном файле и результаты выполнения всех операций не превышают по модулю 10^18.
Выведите последовательно результат выполнения всех операций min. Следуйте формату выход ного файла из примера.
Входные данные
5
1 2 3 4 5
min 2 5
min 1 5
min 1 4
min 2 4
set 1 3 10
add 2 4 4
min 2 5
min 1 5
min 1 4
min 2 4
Выходные данные
2
1
1
2
5
5
8
8
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
ввод: rmq.in
вывод: rmq.out
Рассмотрим массив a[1..n]. Пусть Q(i, j) — ответ на запрос о нахождении минимума среди чисел a[i],..., a[j]. Вам даны несколько запросов и ответы на них. Восстановите исходный массив.
Первая строка входного файла содержит число n — размер массива, и m — число запросов ( 1 ⩽ n, m ⩽ 100 000). Следующие m строк содержат по три целых числа i, j и q, означающих, что Q(i, j) = q( 1 ⩽ _i_⩽ j ⩽ n, -2^31 ⩽ q ⩽ 2^31-1 ).
Если искомого массива не существует, выведите строку «inconsistent». В противном случае в первую строку выходного файла выведите «consistent». Во вторую стро- ку выходного файла выведите элементы массива. Элементами массива должны быть целые числа в интервале от -2^31 до 2^31-1 включительно. Если решений несколько, выведите любое.
Входные данные
3 2
1 2 1
2 3 2
Выходные данные
consistent
1 2 2
Входные данные
3 3
1 2 1
1 1 2
2 3 2
Выходные данные
inconsistent