#1656

Прямоугольники

Темы: [Стек] [Дерево отрезков, RSQ, RMQ]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Кировская открытая областная олимпиада, 2005, Задача E ]

Дана последовательность N прямоугольников различной ширины и высоты (w_i,h_i). Прямоугольники расположены, начиная с точки (0, 0), на оси ОХ вплотную друг за другом (вправо). Требуется найти M - площадь максимального прямоугольника (параллельного осям координат), который можно вырезать из этой фигуры.

Формат входных данных

В первой строке задано число N (1 ≤ N ≤ 8000). Далее идет N строк. В каждой строке содержится два числа: ширина и высота i-го прямоугольника. Значение , 0 < h_i ≤ 3*10⁴.

Формат выходных данных

Вывести одно число М. Значение M не превосходит 2*10⁹.

Примеры

Входные данные

Выходные данные

Входные данные

Выходные данные

#1663

Суперминимум

Темы: [Дерево отрезков, RSQ, RMQ] [Дек]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Кировская открытая областная олимпиада, 2004, Задача D ]

Дано N чисел. Для каждых K подряд идущих чисел найти минимальное среди них.

Формат входных данных

В первой строке даны числа N и K (1 ≤ N ≤ 150000, 1 ≤ K ≤ 10000, K ≤ N), разделенные пробелом. Во второй строке записано N целых чисел через пробел. Числа находятся в диапазоне от -32768 до 32767.

Формат выходных данных

Для каждых К подряд идущих чисел вывести минимальное из них.

Пример

Входные данные

Выходные данные

11 3

8 764 1 3 85 2 4 5 77 1 5

1 1 1 2 2 2 4 1 1

#1672

Спутник

Темы: [Дерево отрезков, RSQ, RMQ]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Кировская открытая областная олимпиада, 2003, Задача F ]

Требуется выполнять две операции: прибавить к ячейке X число Y и определять сумму с L по R.

Секретная корпорация, занимающаяся поиском инопланетных жизненных форм обнаружила на одной из планет созвездия Альфа удивительные живые организмы (даже не плоские, а одномерные). Она приняла решение вести наблюдение за развитием и изменением численности организмов, с этой целью на орбиту планеты был послан спутник - наблюдатель, который мог следить за изменениями численности организмов. Недостаток этого "наблюдателя" в том, что он может отслеживать изменения только на той территории планеты, которая находиться непосредственно под ним.

С этой целью его траектория была разбита на равные интервалы. Они пронумерованы от 1 до N. По запросу с Земли о количестве живых форм в интервале с L по R (L ≤ R) - спутник должен, пролетая над ними (L, L+1, …,R-1, R интервалами) произвести подсчет и затем, в ответ на запрос, отправить полученные данные. Но количество организмов постоянно изменяется: в некоторое время в X интервале на Y единиц.

Помогите написать программу для спутника, которая будет отвечать на запросы и отслеживать количество единиц жизни в каждом интервале.

Формат входных данных

Во входном файле первым записано число N (1 ≤ N ≤ 2¹³ = 8192). Затем записана последовательность событий:

Событие	Параметры	Описание
1	X, Y	Изменение количества организмов в интервале с номером X на Y единиц.(-2¹⁵ ≤ Y ≤ 2¹⁵-1 = 32767)
2	L, R	Запрос суммарного количества организмов с L по R интервал.
0		Завершение работы.

Количество событий не превосходит 100000.

Формат выходных данных

В выходной файл записывать только ответы на запросы.

Примеры

Входные данные

Выходные данные

2

1 1 4

2 1 1

0

4

2 1 4

1 1 3

1 4 2

2 2 4

2 1 2

1 4 -2

1 2 8

2 1 4

0

2

3

11

#111491

Березовая аллея

Темы: [Бинарный поиск по ответу] [Дерево отрезков, RSQ, RMQ]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2013, 1 день, Задача D ]

На краю деревни растет старая березовая аллея. Аллея имеет форму прямой полосы шириной $W$ метров. Вдоль левой стороны аллеи растет $N$ берез, а вдоль правой — $M$ берез, при этом $i$-я береза с левой стороны аллеи находится на расстоянии $a_i$ метров от начала аллеи, а $j$-я береза с правой стороны — на расстоянии $b_j$ метров от начала аллеи.

$\text{[math]}$

Отдыхая в деревне прошедшим летом, один юный информатик обнаружил, что кору берез стали грызть зайцы. Чтобы защитить деревья от зайцев, мальчик решил окружить березы красной лентой (зайцы не любят красный цвет и не станут заходить на огражденную лентой территорию. К сожалению, в его распоряжении оказалась только лента длиной $L$ метров, которую, к тому же, нельзя было разрезать. Единственное, что можно было делать в этом случае — окружить этой лентой как можно больше берез. При этом, чтобы сохранить аллею, необходимо окружить на каждой стороне аллеи хотя бы одну березу.

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

Входные данные

Первая строка входного файла содержит два разделенных пробелом целых числа: длину ленты $L$ и ширину аллеи $W$ ($1 \leq L \leq 2 \times 10^5$, $1 \leq W \leq 10^4$).

Вторая и третья строки описывают березы вдоль левой стороны аллеи. Вторая строка содержит число $N$ — количество берез ($1 \leq N \leq 2000$), а третья строка содержит $N$ различных целых чисел $a_1$, $a_2$, …, $a_N$ ($0 \leq a_i \leq 10^5$), заданных по возрастанию.

Четвертая и пятая строки описывают березы вдоль правой стороны аллеи. Четвертая строка содержит число $M$ — количество берез ($1 \leq M \leq 2000$), а пятая строка содержит $M$ различных целых чисел $b_1$, $b_2$, …, $b_M$ ($0 \leq b_i ≤ 10^5$), заданных по возрастанию.

Выходные данные

Выходной файл должен содержать одно целое число: максимальное количество берез, которое можно оградить заданной лентой.

Гарантируется, что если максимальное число берез, которое можно оградить лентой длины L, равно X, то нет способа оградить (X + 1) березу лентой длины (L + $10^{-5}$).

Система оценивания

Правильные решения для тестов, в которых 1 ≤ N + M ≤ 50, будут оцениваться из 30 баллов.

Правильные решения для тестов, в которых 1 ≤ N + M ≤ 500, будут оцениваться из 60 баллов.

Примеры

Входные данные

Выходные данные

Входные данные

Выходные данные

Страница: 1 Отображать по: