Задача A. Сумма

Входной файл:input.txt   Ограничение времени:10 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

Дан массив из N элементов, нужно научиться находить сумму чисел на отрезке.

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

Первая строка содержит два целых числа N и K — число чисел в массиве и количество запросов. (1 ≤ N ≤ 100 000), (0 ≤ K ≤ 100 000). Следующие K строк содержат запросы

Изначально в массиве живут нули.

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

На каждый запрос вида Q l r нужно вывести единственное число — сумму на отрезке.

Ограничения

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5 9
A 2 2
A 3 1
A 4 2
Q 1 1
Q 2 2
Q 3 3
Q 4 4
Q 5 5
Q 1 5
0
2
1
2
0
5

Задача B. Range Variation Query

Входной файл:rvq.in   Ограничение времени:10 сек
Выходной файл:rvq.out   Ограничение памяти:256 Мб

Условие

В начальный момент времени последовательность an задана следующей формулой: an = n2 mod 12345 + n3 mod 23456.

Требуется много раз отвечать на запросы следующего вида:

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

Первая строка входного файла содержит натуральное число k — количество запросов (1 ≤ k ≤ 100 000).

Следующие k строк содержат запросы, по одному на строке. Запрос номер i описывается двумя целыми числами xi, yi.

Если xi > 0, то требуется найти разность между максимальным и минимальным значениями среди элементов axi, …, ayi. При этом 1 ≤ xi ≤ yi ≤ 100 000.

Если xi < 0, то требуется присвоить элементу a|xi| значение yi.

В этом случае  − 100 000 ≤ xi ≤  − 1 и |yi| ≤ 100 000.

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

Для каждого запроса первого типа в выходной файл требуется вывести одну строку, содержащую разность между максимальным и минимальным значениями на соответствующем отрезке.

Ограничения

Примеры тестов

Входной файл (rvq.in) Выходной файл (rvq.out)
1
7
1 3
2 4
-2 -100
1 5
8 9
-3 -101
2 3
34
68
250
234
1

Задача C. Сумма+присвоение на отрезке

Входной файл:sum.in   Ограничение времени:10 сек
Выходной файл:sum.out   Ограничение памяти:256 Мб

Условие

Дан массив из N элементов, нужно научиться находить сумму чисел на отрезке.

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

Первая строка входного файла содержит два целых числа N и K — число чисел в массиве и количество запросов. (1 ≤ N ≤ 100 000), (0 ≤ K ≤ 100 000). Следующие K строк содержат запросы:

Изначально массив заполнен нулями.

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

На каждый запрос вида

Q l r
нужно вывести единственное число — сумму на отрезке.

Ограничения

Примеры тестов

Входной файл (sum.in) Выходной файл (sum.out)
1
5 9
A 2 3 2
A 3 5 1
A 4 5 2
Q 1 3
Q 2 2
Q 3 4
Q 4 5
Q 5 5
Q 1 5
3
2
3
4
2
7

Задача D. RMQ

Входной файл:rmq.in   Ограничение времени:2 сек
Выходной файл:rmq.out   Ограничение памяти:256 Мб

Условие

Дан массив a[1..n]. Требуется написать программу, обрабатывающую два типа запросов.

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

Первая строка содержит два целых числа n и q (1 ≤ n, q ≤ 105) — длина массива и число запросов соответственно.

Вторая строка содержит n целых чисел a1, …, an (|ai| ≤ 105), задающих соответствующие значения массива.

Следующие q строк содержат запросы.

В зависимости от типа запрос может иметь вид либо «max l r», либо «add l r v».

1 ≤ l ≤ r ≤ n, |v| ≤ 105.

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

Для каждого запроса вида «max l r» требуется в отдельной строке выдать значение соответствующего максимума.

Ограничения

Примеры тестов

Входной файл (rmq.in) Выходной файл (rmq.out)
1
5 3
1 2 3 4 -5
max 1 3
add 1 2 5
max 1 3
3
7

Задача E. Выборы заведующего кафедрой

Автор:Г. Гренкин, И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

В ДВФУ произошло укрупнение кафедры информатики. В связи с этим встал вопрос выборе нового заведующего кафедрой. На кафедре работает много преподавателей и непросто выбрать самого достойного. Посовещавшись, преподаватели занумеровали себя и для преподавателя с номером i определили следующие числа:

Чем больше число, тем выше уровень мастерства преподавателя в соответствующей области.

Считается, что, i-й преподаватель является кандидатом на должность заведующего кафедрой в том и только том случае, когда для него не найдётся такого j-того преподавателя, что одновременно mj > mi, pj > pi, tj > ti.

Напишите программу, составляющую список кандидатов на должность заведующего кафедрой.

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

Входной файл содержит натуральное число n  — количество преподавателей. Далее следует n троек натуральных чисел mi pi ti.

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

Требуется вывести в выходной файл номера отобранных преподавателей в порядке возрастания.

Ограничения

1 ≤ n ≤ 105

1 ≤ mi, pi, ti ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4
2 3 4
1 1 3
2 1 8
3 2 10
1 4

0.234s 0.008s 21