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

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

ДЗ #11, Деревья отрезков

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

Содержание

Must have 2

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

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

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

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

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

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

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

Во всех задачах запрещается использовать сбалансированные BST .

Во многих задачах BST не прошли бы TL естественным путём.. .

Страница 1 из 11 ДЗ #11, Деревья отрезков СПб, Академический Университет, 11 мая 2017 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

–  –  –

Задача 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 .

Страница 3 из 11 ДЗ #11, Деревья отрезков СПб, Академический Университет, 11 мая 2017 Обязательные задачи Задача 11C. Минимум и максимум [0.3 sec, 256 mb] В этой задаче обязательно использовать дерево отрезков .

Пусть есть мультимножество целых чисел (множество с возможными повторениями) .

Необходимо реализовать структуру данных для их хранения, поддерживающую следующие операции: GetMin — извлечение минимума, GetMax — извлечение максимума, Insert(N) — добавление числа в множество .

Формат входных данных В первой строке входного файла записано одно целое число (1 100 000) — число запросов к структуре. Затем в строках следуют запросы по одному в строке: GetMin, GetMax, Insert(A) извлечение минимума, максимума и добавление числа (1 231 1) .

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

Формат выходных данных Для каждого запроса GetMin или GetMax выведите то число, которое было извлечено .

Примеры stdin stdout Insert(100) 100 Insert(99) 1 Insert(1) 2 Insert(2) 99 GetMin GetMax Insert(1) GetMin GetMin GetMax Замечание Можно сжать координаты.. .

Но проще использовать динамическое дерево отрезков .

–  –  –

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

–  –  –

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

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

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

Примеры stdin stdout

–  –  –

Задача 11J. Треугольник [6 sec, 512 mb]

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

добавить точку в множество;

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

–  –  –

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

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

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

«Утвержден на заседании Президиума ВФГБК "30" ноября 2015 г. (протокол №11/15) ОТБОР СПОРТСМЕНОВ И ФОРМИРОВАНИЕ СБОРНЫХ КОМАНД РОССИИ по гребле на байдарках и каноэ на 2016 год Система отбора в...»

«Раздел 2. Неравномерное кодирование дискретных источников. В предыдущем разделе мы убедились в том, что источники информации, вообще говоря, избыточны в том смысле, что, при эффективном кодировании можно уменьшить затраты на передачу или хранение порождаемой ими информации. Для представления данных потребу...»

«Вадим Витальевич Тихомиров Пчеловодство для начинающих http://www.litres.ru/pages/biblio_book/?art=6996557 В. В. Тихомиров. Пчеловодство для начинающих: АСТ; Москва; 2014 ISBN 978-5-17-083796-0 Аннотация Эта книга посвящена проблемам практического пчеловодств...»

«Вариант № 786504 1. B 1 № 337415. Найдите значение выраж ения Решение.Умнож им числитель и знаменатель на 100: Ответ: 37,5.2. A 1 № 314156. Одна из точек, отмеченных на координатной прямой, соответствует числу Какая это точка?1) точка...»

«Плутарх Сравнительные жизнеописания http://www.litres.ru/pages/biblio_book/?art=2572425 Сравнительные жизнеописания / Пер. с древнегреческого: Аннотация "Жизнеописания" Плутарха не тольк...»

«Дуглас Адамс Путеводитель вольного путешественника по Галактике Книга II. Ресторан “На Конце света” пер. Степан М. Печкин, 2004 Издание Трансперсонального Института Человека Печкина The Hitchhiker's Guide to the Galaxy, © 1979 by Douglas Adams Translation © Stepan M. Pechkin, 2004 (p) Pechkin Production...»

«МБДОУ "Детский сад им. Ю.А.Гагарина" СЕМИНАР-ПРАКТИКУМ Тема: "POP-UP ОДНА ИЗ ТЕХНИК КАРДМЕЙКИНГА" Подготовила и провела воспитатель Иванова Светлана Геннадьевна 23.01.2017 год Гагарин 1 слайд. Заставка 2 слайд. Кардмейкинг, это загадочное слово давно и прочно вошло в нашу жизнь, и не только в среде хэндмейкеров, мы встречае...»

«АПОСТОЛ, 196-197 ЗАЧАЛА (КОММ. НА 2 КОР. 12:19-13) ВТОРНИКА 14 НЕДЕЛИ 12:20-13:2 СРЕДЫ 14 НЕДЕЛИ 13:3-13 ЦЕРКОВНОСЛАВЯНСКИЙ ТЕКСТ (12:20-13:13) СИНОДАЛЬНЫЙ ПЕРЕВОД (12:19-13:13) ИОАНН ЗЛАТОУСТ (Стихи 12:19-21) (Добродетель светлее солнца, а порок смраднее навоза) (Ирод, не снося стыда от обличений, вверг в темницу Иоанна) (Так сильно боял...»






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

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