WWW.NEW.PDFM.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Собрание документов
 

«Содержание Must have 2 Задача 11A. Сумма [0.3 sec, 256 mb] 2 Задача 11B. Звёзды [0.1 sec, 256 mb] 3 Обязательные задачи 4 Задача 11C. RMQ [0.5 sec, 256 mb] 4 Задача 11D. Художник [1.5 sec, 256 mb] 5 ...»

1-й курс, весна, ДЗ #11, Деревья отрезков

СПб, Академический Университет, 9 мая 2018

Содержание

Must have 2

Задача 11A. Сумма [0.3 sec, 256 mb] 2

Задача 11B. Звёзды [0.1 sec, 256 mb] 3

Обязательные задачи 4

Задача 11C. RMQ [0.5 sec, 256 mb] 4 Задача 11D. Художник [1.5 sec, 256 mb] 5 Задача 11E. Окна [0.6 sec, 256 mb] 6 Задача 11F. Прямоугольники [0.6 sec, 256 mb] 7 Дополнительные задачи 8 Задача 11G. k-я статистика на отрезке [6.5 sec, 256 mb] 8 Задача 11H. Различные числа [1.5 sec, 256 mb] 9 Задача 11I. Треугольник [7 sec, 256 mb] 10 Вы не умеете читать/выводить данные, открывать файлы? Воспользуйтесь примерами .

В некоторых задачах большой ввод и вывод. Пользуйтесь быстрым вводом-выводом .

В некоторых задачах нужен STL, который активно использует динамическую память (set-ы, map-ы) переопределение стандартного аллокатора ускорит вашу программу .

Обратите внимание на компилятор GNU C++11 5.1.0 (TDM-GCC-64) inc, который позволяет пользоваться дополнительной библиотекой. Под ним можно сдать вот это .

Страница 1 из 10 1-й курс, весна, ДЗ #11, Деревья отрезков СПб, Академический Университет, 9 мая 2018 Must have Задача 11A. Сумма [0.3 sec, 256 mb] Дан массив из элементов, нужно научиться находить сумму чисел на отрезке .

Формат входных данных Первая строка содержит два целых числа и — число чисел в массиве и количество запросов. (1 100 000), (0 100 000). Следующие строк содержат запросы “A i x” — присвоить -му элементу массива значение (1, 0 109 ) “Q l r” — найти сумму чисел в массиве на позициях от до. (1 ) Изначально в массиве живут нули .



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

Примеры stdin stdout A 2 2 2 A 3 1 1 A 4 2 2 Q 1 1 0 Q 2 2 5 Q 3 3 Q 4 4 Q 5 5 Q 1 5 Замечание Обыкновенное дерево отрезков .

Попробуйте написать “снизу”, получится супер короткий и простой код .

–  –  –

Задача 11B. Звёзды [0.1 sec, 256 mb] Астрономы часто исследуют звёздные карты, на которых звёзды представлены точками на плоскости, каждая звезда имеет декартовы координаты. Пусть уровень звезды – количество звёзд, которые не выше и не правее данной звезды. Астрономы хотят найти распределение уровней звёзд .

Для примера посмотрим на карту звёзд на картинке выше. Уровень звезды номер 5 равен 3 (т.к. есть звёзды с номерами 1, 2, 4). Уровни звёзд 2 и 4 равны 1. На данной карте есть только одна звезда на уровне 0, две звезды на уровне 1, одна звезда на уровне 2 и одна звезда на уровне 3. Напишите программу, считающую количество звёзд на каждом уровне .

Формат входных данных Вам дан один или несколько тестов. Каждый тест описывается следующим образом .

В первой строке количество звёзд (1 15 000). Следующие строк описывают координаты звёзд (два целых числа и, разделённые пробелом, 0, 32, 000). В каждой точке плоскости находится не более одной звезды. Звёзды перечислены в порядке возрастания координаты, при равенстве в порядке возрастания координаты .

Формат выходных данных Выведите ответ для каждого теста. Ответ для теста описывается следующим образом .

строк, по одному числу в строке. -я строка содержит количество звёзд на уровне ( = 0... 1) .

Примеры stdin stdout Замечание Простейший scanline .

–  –  –

Задача 11E. Окна [0.6 sec, 256 mb] На экране расположены прямоугольные окна, каким-то образом перекрывающиеся (со сторонами, параллельными осям координат). Вам необходимо найти точку, которая покрыта наибольшим числом из них .





Формат входных данных В первой строке входного файла записано число окон (1 50 000) .

Следующие строк содержат координаты окон (1,) (1,) (2,) (2,), где (1,), (1,) — координаты левого верхнего угла -го окна, а (2,), (2,) — правого нижнего (на экране компьютера растет сверху вниз, а — слева направо) .

Все координаты — целые числа, по модулю не превосходящие 2 · 105 .

Формат выходных данных В первой строке выходного файла выведите максимальное число окон, покрывающих какую-либо из точек в данной конфигурации. Во второй строке выведите два целых числа, разделенные пробелом — координаты точки, покрытой максимальным числом окон. Окна считаются замкнутыми, т.е. покрывающими свои граничные точки .

Пример stdin stdout Замечание Scanline. Похожая задача разобрана на практике .

Страница 6 из 10 1-й курс, весна, ДЗ #11, Деревья отрезков СПб, Академический Университет, 9 мая 2018 Задача 11F. Прямоугольники [0.6 sec, 256 mb] На плоскости задано прямоугольников, никакие два из которых не имеют общих точек .

В каждом прямоугольнике записано целое число .

Скажем, что прямоугольник лежит дальше прямоугольника, если левый верхний угол прямоугольника лежит строго ниже и правее правого нижнего угла прямоугольника .

Последовательность прямоугольников 1, 2,..., назовем цепью, если для всех прямоугольник лежит дальше прямоугольника 1. Весом цепи назовем сумму чисел, записанных во входящих в нее прямоугольниках .

Требуется найти цепь прямоугольников с максимальным весом .

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

Пусть ось направлена слева направо, а ось — снизу вверх. Следующие строк содержат по пять целых чисел — координаты,1,,1 левого нижнего,,2,,2 правого верхнего углов прямоугольника и — число, записанное в прямоугольнике. Координаты не превышают 109 по абсолютной величине. Числа, записанные в прямоугольниках, положительные и не превышают 109. Ни один прямоугольник не лежит внутри другого .

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

Пример stdin stdout Замечание Продолжаем тренировать scanline. Предполагается, что это решение получается копированием уже сданной и уже написанного дерева отрезков с нужными операциями .

–  –  –

Задача 11H. Различные числа [1.5 sec, 256 mb] Сколько различных чисел на отрезке массива?

Формат входных данных На первой строке длина массива (1 300 000). На второй строке целых чисел от 0 до 109 1. На третьей строке количество запросов (1 300 000). Следующие строк содержат описание запросов, по одному на строке. Каждый запрос задаётся парой целых чисел, (1 ) .

Формат выходных данных Выведите ответы на запросы по одному в строке .

Примеры stdin stdout

–  –  –

Задача 11I.

Треугольник [7 sec, 256 mb] Ваша задача — написать программу, хранящую мультимножество точек и позволяющую отвечать на запросы двух видов:

добавить точку в множество, посчитать количество точек множества, лежащих внутри или на границе данного треугольника .

–  –  –

Подсказка по решению Есть setint с операциями order_of_key и find_by_order. Называется treeint .

Разобраться, как им пользоваться, можно, прочитав пост на codeforces.

Похожие работы:

«ФАКУЛЬТЕТ ЖУРНАЛИСТИКИ МГУ ИМЕНИ М. В. ЛОМОНОСОВА Профессора, преподаватели и научные сотрудники ф акультета журналистики Московского университета БИОГРАФИЧЕСКИЙ СЛОВАРЬ Москва 2012 Ф а культет ж у рнал и сти ки М о с к о в с к о го госуд ар ствен н о го университета имени М. В. Л ом оносова ББК 7...»

«Памяти защитников Отечества посвящается МИНИСТЕРСТВО ОБОРОНЫ РОССИЙСКОЙ ФЕДЕРАЦИИ ВЕЛИКАЯ ОТЕЧЕСТВЕННАЯ ВОЙНА 1941–1945 ГОДОВ В ДВЕНАДЦАТИ ТОМАХ Председатель А. Э . СЕРДЮКОВ A. И. АГЕЕВ, С. А. АРИСТОВ, В. П. БАРАНОВ, С. П. БУЛАВИН, А. Е. БУСЫГИН, А. Т. ВАХИДОВ, B. С. ВЫСОЦКИЙ, М. А. ГАРЕЕВ, А. Н. ЕФИМОВ,...»

«САМОЛЕТОВОЖДЕНИЕ ВОЗДУШНАЯ СКОРОСТЬ ПОЛЕТА. Устройства и применение указателей воздушной скорости Аэродинамический метод измерения воздушной скорости Воздушной скоростью полета называется скорость перемещения самолета относительно воздушной среды. При этом различают истинную воздушную скорость и приборную скорость....»

«Оглоблин Г.В., Рыков. Д. В., Долгов В.Ю. АмГПГУ, Комсомольск-на-Амуре, Россия ПОГЛОЩЕНИЕ ЭЛЕКТРОМАГНИТНОЙ ВОЛНЫ ОТРАЖЕННОЙ ОТ ПОВЕРХНОСТИ МЕТАЛЛ –КЕРАМИКА. Рассматривается вопрос поглощения электромагнитных волн СВЧ д...»

«ЦЕЛИ ОСВОЕНИЯ ДИСЦИПЛИНЫ Целью обучения эргономике является изучение и освоение общих положений о приспособлении труда к физиологическим возможностям человека, выявление закономерностей создани...»

«Азербайджанские сказки Зарнияр Мухтар Немая царевна Тахта-клыдж Ученик портного Овчи-Пирим От судьбы не уйдёшь Ленивый Ахмед Пёс Шехсеванского Гаджи Сказка о шахе Аман-шахе и его трех сыновьях Соловей ха...»

«СТРУКТУРНАЯ ГЕОЛОГИЯ Лекция 6 Складчатость Геологи-2016_ л6_Милосердова 1 Совокупность складок образует складчатость. Если складки по разрезу повторяют друг друга, такую складчатость называют гармонической. Попробуйте классифициров ать одиночные складки, изображенные на разрезах. Это складки, сложенные палеогеновыми, меловыми и юрскими...»

«Глава 7 Винтики гигантской машины Запах Грили вы почуете задолго до того, как увидите сам город. Этот "аромат" трудно забыть и нелегко описать: сочетание запаха живых животных, навоза и забитых животных, из которых делают корм для собак. Запах еще сильнее в летние месяцы. Он окутывает город невидимой...»






 
2018 www.new.pdfm.ru - «Бесплатная электронная библиотека - собрание документов»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.