Маленький мальчик Глеб еще толком не познал жизнь, но он уже ОЧЕНЬ любит КАРАТЬ, НЕ ПРОЩАТЬ! И вот в очередной раз он решил поиздеваться над бедным Лёшиком =(
Он сказал, что у него есть первая четверть плоскости, он умеет добавлять на нее прямоугольник с нижней левой точкой (0;0) и верхней правой (x;y), умеет считать площадь получившейся фигуры, умеет считать площадь объединения этой фигуры с прямоугольником на точках (x1;y1) и (x2;y2) и даже площадь пересечения.
Лёшик в печальке... =(
Спасите Лёшика, решите эту задачу. Но помните, Глеб настолько суров, что заставил решать поставленную задачу в он-лайне!!!
В первой строке задано число N (1 ≤ N ≤ 105). Далее следует описание запросов:
первое число t — тип запроса
t = 0: вводятся числа x и y, значит нужно добавить прямоугольник с координатами (0;0) и (x;y)
t = 1: вы должны вывести площадь получившейся фигуры
t = 2: вводятся числа x1, y1, x2, y2, значит нужно вывести площадь пересечения фигуры и такого прямоугольника
t = 3: вводятся числа x1, y1, x2, y2, значит нужно вывести площадь объединения фигуры и такого прямоугольника
Так как Глеб коварен, то все числа в запросах нужно еще преобразовать. Пусть ANS — ответ на предыдущий запрос. Изначально ANS = 0.
Тогда при t = 0 x = 1 + (x + ANS): mod: 109, y = 1 + (y + ANS): mod: 109.
При t = [2, 3] x1 = 1 + (x1 + ANS): mod: (5·108), y1 = 1 + (y1 + ANS): mod: (5·108), x2 = x1 + 1 + (x2 + ANS): mod: (5·108), y2 = y1 + 1 + (y2 + ANS): mod: (5·108).
После запросов типа 1, 2 или 3 ANS = ответу на этот запрос.
Выведите ответы на запросы.
В 1 примере даны запросы, которые не преобразуются по заданным формулам для простоты понимания.
4 0 2 2 1 2 1 1 3 3 3 1 1 3 3
9 0 24
4 0 2 2 1 2 1 1 3 3 3 1 1 3 3
9 0 24
Задано подвешенное дерево, содержащее n (1 ≤ n ≤ 100000) вершин, пронумерованных от 0 до n - 1. Требуется ответить на m (1 ≤ m ≤ 100000) запросов о наименьшем общем предке для пары вершин.
Запросы генерируются следующим образом. Заданы числа a1, a2 и числа x, y и z. Числа a3, ..., a2m генерируются следующим образом: ai = (x·ai - 2 + y·ai - 1 + z)mod: n. Первый запрос имеет вид (a1, a2). Если ответ на (i - 1)-й запрос равен v, то i-й запрос имеет вид ((a2i - 1 + v)mod: n, a2i).
Первая строка содержит два числа: n и m. Корень дерева имеет номер 0. Вторая строка содержит n - 1 целых чисел, i-е из этих чисел равно номеру родителя вершины i. Третья строка содержит число содержит два целых числа в диапазоне от 0 до n - 1: a1 и a2. Четвертая строка содержит три целых числа: x, y и z, эти числа неотрицательны и не превосходят 109.
Выведите в выходной файл сумму номеров вершин — ответов на все запросы.
3 2 0 1 2 1 1 1 0
2
Злобный учитель в MШП любит мучить детей сложными задачками. А если дети эти задачки не решают, учитель подвергает их самым жестоким наказаниям. На этот раз он придумал такую задачу:
Рейтинг всех учеников МШП записан в массив A
Запросы учителя таковы:
Помогите бедным ученикам МШП избежать зверского наказания за нерешение задачи на этот раз.
В первой строке входного файла записано число N (1 ≤ N ≤ 500000) – количество учеников в МШП. Во второй строке записано N чисел – их рейтинги, числа по модулю не превосходящие 1000 (по количеству задач, которые ученик решил или не решил за время обучения). В третьей строке записано число M (1 ≤ M ≤ 50000) – количество запросов. Каждая из следующих M строк содержит описания запросов:
UPDATE i x – обновить i-ый элемент массива значением x (1 ≤ i ≤ N, |x| ≤ 1000)
QUERY l r – найти длину максимальной последовательности из нулей на отрезке с l по r. (1 ≤ l ≤ r ≤ N)
В выходной файл выведите ответы на запросы QUERY в том же порядке, что и во входном файле
5 328 0 0 0 0 5 QUERY 1 3 UPDATE 2 832 QUERY 3 3 QUERY 2 3 UPDATE 2 0
2 1 1
На экране расположены прямоугольные окна, каким-то образом перекрывающиеся (со сторонами, параллельными осям координат). Вам необходимо найти точку, которая покрыта наибольшим числом из них.
В первой строке входного файла записано число окон n (1 ≤ n ≤ 50 000). Следующие n строк содержат координаты окон x(1, i) y(1, i) x(2, i) y(2, i), где (x(1, i), y(1, i)) — координаты левого верхнего угла i-го окна, а (x(2, i), y(2, i)) — правого нижнего (на экране компьютера y растет сверху вниз, а x — слева направо). Все координаты — целые числа, по модулю не превосходящие 106.
В первой строке выходного файла выведите максимальное число окон, покрывающих какую-либо из точек в данной конфигурации. Во второй строке выведите два целых числа, разделенных пробелом — координаты точки, покрытой максимальным числом окон. Окна считаются замкнутыми, т. е. покрывающими свои граничные точки.
2 0 0 3 3 1 1 4 4
2 1 3
1 0 0 1 1
1 0 1
4 0 0 1 1 0 1 1 2 1 0 2 1 1 1 2 2
4 1 1
5 0 0 1 1 0 1 1 2 0 0 2 2 1 0 2 1 1 1 2 2
5 1 1
Джек нашел \(N\) камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер 1, следующий 2 и так далее, самый тяжелый получил номер \(N\).
У Джека есть чашечные весы и он решил положить все камни на них в каком-то порядке. Известен порядок, в котором он будет класть камни, и какой камень на какую чашу попадет.
Ваша задача — определить состояние весов после добавления каждого камня. Точные массы камней не известны — даются только их номера.
Первая строка содержит целое число \(N\) (1 \(\le\) \(N\) \(\le\) 100000).
Каждая из следующих \(N\) строк содержит по два целых числа: \(R\) (1 \(\le\) \(R\) \(\le\) \(N\)) и \(S\) (1 \(\le\) \(S\) \(\le\) 2). \(R\) номер камня, который будет положен на чашу \(S\). Все \(R\) будут различны.
Выведите \(N\) строк по одной для каждого камня. Если после добавления соответствующего камня чаша 1 тяжелее, выведите “<”. Если сторона 2 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.
5 1 2 3 1 2 1 4 2 5 1
< > > ? >