--->
90 задач
<---
Источники
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
В новых элитных электричках каждому пассажиру положено сидячее место. Естественно, количество сидячих мест ограничено и на всех их может не хватить. Маршрут электрички проходит через N+1 станция, занумерованные от 0 до N. Когда человек хочет купить билет, он называет два числа x и y – номера станций, откуда и куда он хочет ехать. При наличии хотя бы одного сидячего места на этом участке на момент покупки ему продается билет, иначе выдается сообщение «билетов нет» и билет не продается. Ваша задача – написать программу, обслуживающую такого рода запросы в порядке их прихода.
Входные данные
В первой строке содержаться три числа N – количество станций (1 ≤ N ≤ 200 000), K – количество мест в электричке (1 ≤ K ≤ 1000) и M – количество запросов (1 ≤ M ≤ 100 000). В следующих M строках описаны запросы, каждый из которых состоит из двух чисел x и y (0 ≤ x < y <= N).
Выходные данные
На каждый запрос ваша программа должна выдавать результат в виде числа 0 если билет не продается и 1 если билет был продан. Каждый результат должен быть на отдельной строке
Примеры
Входные данные
5 2 4 0 4 1 2 1 4 2 4
Выходные данные
1 1 0 1
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes
Служба электроснабжения проводит мониторинг уровня снега, лежащего на ЛЭП Нью-Васюки - Москва. Вся ЛЭП разбивается на участки опорами. Снег имеет свойства падать на какой-либо интервал ЛЭП, если там уже лежал какой-либо снег, то высота снежного покрова на этом участке суммируется. Также снег имеет тенденцию таять на участке трассы в результате оттепели, при этом известно, что не бывает сугробов отрицательной высоты. Энергетикам крайне важно уметь узнавать суммарную высоту снежного покрова на некоторых последовательных участках, чтобы знать вероятность обрыва проводов.
Входные данные
В первой строке входного файла содержатся два числа: N – (1 ≤ N ≤ 10 000) и M – количество команд (1 ≤ M ≤ 50 000). Каждая команда имеет вид “1 L R S”, что означает, что на участок с L-ой опоры по R-ую опору выпало S сантиметров снега (S может быть и отрицательным, тогда это означает, что такое количества снега растаяло), или “2 L R” – запрос суммарной высоты снега на участке с L-ой опоры по R-ую. Опоры нумеруются от 0 до N. Гарантируется, что для запросов вида “1 L R S” при S < 0 на каждом участке между опорами L и R уровень снега составляет не менее S.
Выходные данные
На каждую команду 2 (запрос) вы должны выводить число K – суммарную высоту снежного покрова, лежащего на проводах с L-ой опоры по R-ую. Каждое число должно выводиться на новой строке. Известно, что в процессе работы суммарное количество снега на любом интервале не превышает 231.
Примеры
Входные данные
10 5 1 0 9 10 1 1 5 -3 2 4 8 1 0 6 25 2 0 2
Выходные данные
37 67
#1638
Темы:
[Дерево отрезков, RSQ, RMQ]
Ограничение по времени: 0.2 секунды
На планете Олимпия рабочие строят новую дамбу. Часть плоскости, на которой проводятся строительные работы, имеет вид прямоугольника размером 1 x \(L\) метров, на котором введены координаты, как показано на рисунке.
Для поднятия ландшафта используют специально разработанные магические импульсаторы. Если магический импульсатор силой \(H\) поставить в точку с \(X\)-координатой \(p\), то в каждой точке \(q\) отрезка [\(p\)–\(H\);\(p\)] на оси \(X\) рельеф поднимается на \(q\)–\(p\)+\(H\) метров по всей его ширине (то есть для произвольного \(Z\) от 0 до 1), а в каждой точке \(q\) отрезка [\(p\);\(p\)+\(H\)] рельеф поднимается на \(H\)+\(p\)–\(q\) метров по всей его ширине, в остальных точках ландшафт остается неизменным (см. рисунок).
Во время строительства рабочие время от времени интересуются объёмом части дамбы, находящейся над некоторым прямоугольником.
Напишите программу, которая поможет рабочим в их расчётах.
Входные данные
В первой строке входного файла содержатся два целых числа: N – количество операций, которые будут выполнять рабочие (1≤\(N\)≤100000), и \(L\) – длина прямоугольника (1≤\(L\)≤100000).
В следующих \(N\) строках содержатся описания операций: первое число строки – номер операции, где „1” означает, что рабочие собираются поставить магический импульсатор, „2” – рабочие хотят узнать некоторый объём. Если операция имеет код „1”, то далее идут два целых числа \(p\) и \(H\) (0≤\(p\)≤\(L\); 1≤\(H\)≤\(L\)), то есть импульсатор силой \(H\) ставят в позицию p (на оси \(X\)). Если операция имеет код „2”, то далее идут два целых числа \(A\) и \(B\) (0≤\(A\)<\(B\)≤\(L\)); это означает, что рабочие хотят узнать объём части дамбы, которая находится над прямоугольником от \(A\) до \(B\) по оси \(X\), и от 0 до 1 по оси \(Z\).
Выходные данные
Создайте выходной файл, в котором для каждой операции, указанной во входном файле, выведите строку со следующей информацией.
Если операция есть „1”, то выведите число „-1” без кавычек. Если операция есть „2”, то выведите число округленное вниз до ближайшего целого, равное объёму части дамбы, которая находится над прямоугольником от \(A\) до \(B\) по оси \(X\), и от 0 до 1 по оси \(Z\), как показано на рисунке.
Примеры
Входные данные
2 13 1 7 5 2 5 9
Выходные данные
-1 16
#1656
Темы:
[Стек]
[Дерево отрезков, RSQ, RMQ]
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Региональный этап,
Кировская открытая областная олимпиада,
2005,
Задача E
]
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes
Дана последовательность N прямоугольников различной ширины и высоты (wi,hi). Прямоугольники расположены, начиная с точки (0, 0), на оси ОХ вплотную друг за другом (вправо). Требуется найти M - площадь максимального прямоугольника (параллельного осям координат), который можно вырезать из этой фигуры.
Формат входных данных
В первой строке задано число N (1 ≤ N ≤ 8000). Далее идет N строк. В каждой строке содержится два числа: ширина и высота i-го прямоугольника. Значение 
, 0 < hi ≤ 3*104.
Формат выходных данных
Вывести одно число М. Значение M не превосходит 2*109.
Примеры
Входные данные
3 4 3 2 1 2 5
Выходные данные
12
Входные данные
3 4 3 2 1 3 5
Выходные данные
15
#1663
Темы:
[Дерево отрезков, RSQ, RMQ]
[Дек]
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Региональный этап,
Кировская открытая областная олимпиада,
2004,
Задача D
]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Дано 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 |
Выбрано
:
|