задачи (деревья отрезков)

Задача 1. Галактика
Входной файл: galaxy.in
Выходной файл: galaxy.out
Ограничение памяти: 128 М байт
Ограничение времени: 2 секунды на тест
В Галактике N обитаемых планет. Для обеспечения населения мобильной связью Галактический Совет планирует установить на двух планетах ретрансляционные станции. К сожалению, мощность имеющихся ретрансляторов не столь велика, как хотелось бы, и есть опасение, что не все планеты окажутся в зоне действия станций. Вы должны написать программу, которая будет вычислять количество планет, находящихся в зоне действия хотя бы одного из ретрансляторов. Планета считается находящейся в зоне действия ретранслятора, если расстояние от неё, до планеты, где установлен ретранслятор, не превышается заданного радиуса действия ретранслятора.
Вход
В первой строке входного файла записано количество планет N (3
· N
· 500000). В следующих N строках содержатся целочисленные декартовы координаты планет xi, yi, zi (-500000
· xi, yi, zi
· 500000). Ретрансляторы установлены на первой и второй планете. В следующей строке записано количество запросов Q (1
· Q
· 500000). И последние Q строк файла содержат Q пар целых чисел R1, R2 – радиусы действия первого и второго ретрансляторов (1
· R1, R2
· 107).
Выход
Для каждого запроса запишите в выходной файл количество планет, попадающих в зону действия хотя бы одного ретранслятора.
Примеры входа и выхода
galaxy.in
galaxy.out

5
1 1 1
5 5 5
2 2 2
3 3 3
4 4 4
4
1 1
2 1
2 2
6 6
2
3
4
5


Задача 2. Монеты
Входной файл: coins.in
Выходной файл: coins.out
Ограничение памяти: 128 М байт
Ограничение времени: 1 секунда на тест
Белый Кролик поступил на госслужбу, и теперь у него в норе N ящиков с золотыми монетами, пронумерованных от 1 до N. Мартовский Заяц интересуется, сколько всего монет у Белого Кролика (он тоже подумывает о поступлении на госслужбу), но Кролик не хочет отвечать. Мартовский Заяц придумал такую хитрость. Он говорит Кролику – «ну ладно, не хочешь говорить – не говори, но скажи хотя бы, какое минимальное количество монет лежит у тебя в ящиках с номерами от a до b включительно». На такие вопросы Белый Кролик соглашается отвечать. Мартовский Заяц задал много вопросов и получил много ответов. Теперь он нуждается в программе, которая может найти минимально возможное количество золотых монет у Белого Кролика.
Вход
В первой строке входного файла записаны целые числа N – количество ящиков с монетами и Q – количество вопросов, заданных Мартовским Зайцем (1
· N
· 109 , 1
· Q
· 105). В остальных строках содержится Q троек целых чисел a, b, m (1
· a
· b
· N, 0
· m
· 109), где a, b - заданный Мартовским Зайцем вопрос, а m – ответ Белого Кролика.
Выход
Запишите в выходной файл минимально возможное количество золотых монет у Белого Кролика. Если ответы Кролика противоречивы, запишите в выходной файл число -1 (минус единица).
Примеры входа и выхода
coins.in
coins.out

1000000000 1
1 1000000000 0
0

1000000000 1
1 1000000000 5
5000000000

1000000000 3
3 4 1 5 6 10 4 5 100
211

1000000000 3
3 4 100 5 6 10 4 5 1
-1

1000000000 5
6 6 1000 4 4 100 3 4 10
4 5 10 3 6 10
1120



Задача 3. «Блинчики»
Входной файл: pancakes.in
Выходной файл: pancakes.out
Ограничение времени: 1 секунда на тест
Ограничение памяти: 64 М байт

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

Итак, фирма В. Пупкина изготовила и продала a1, a2, , an блинчиков за первые n дней своего существования. Эти данные Пупкин вам предоставит. В каждый из дней, начиная со второго, вы должны вычислить величину bj, равную количеству чисел, не превосходящих aj среди a1, , aj-1. Чтобы проверить, насколько правильно работает ваша программа, заказчик попросил для начала вычислить сумму b2 + b3 + + bn.

Вход
В первой строке входного файла записано число n – время существования фирмы в днях (2
· n
· 100000). В остальных строках записаны числа a1, a2, , an (0
· ai
· 109).

Выход
Запишите в выходной файл сумму b2 + b3 + + bn.

Примеры входа и выхода
pancakes.in
pancakes.out

5
4 3 2 1 0
0

5
0 1 2 3 4
10



Задача 4. «Выборы»
Входной файл: election.in
Выходной файл: election.out
Ограничение времени: 2 секунды на тест
Ограничение памяти: 64 М байт

Скоро в Тьмутараканском Удельном Княжестве выборы в боярскую думу. За места в думе борются две главные политические коалиции – «Свободная Тьмутаракания» и «Красивая Тьмутаракания». Поскольку никому пока не удалось обнаружить ни одного отличия в платформах этих коалиций, их для простоты обозначают буквами A и B. Для предвыборной агитации в центре Тьмутараканска воздвигнут рекламный щит размером 10.24 метра на 10.24 метра, разделённый на 1024 * 1024 квадратных ячеек площадью в 1 кв. см. Каждая из коалиций заготовила большое количество квадратных наклеек размером 1 на 1 см, на которых, соответственно, написана буква А или буква В. Первоначально активисты коалиций заклеили рекламный щит своими наклейками в шахматном порядке, вот так
ABABABAB
BABABABA
ABABABAB
BABABABA
.....................
При этом в левом верхнем углу оказалась буква «А». В ночь перед выборами, стремясь получить преимущество, активисты коалиций скрытно подобрались к щиту и принялись наклеивать на него свои буквы. После того, как сверху наклеивалась буква, прежняя буква становилась полностью невидимой. В спешке активисты нередко заклеивали и свои собственные буквы. Вся эта незаконная деятельность была заснята многочисленными камерами наблюдения, установленными в центре Тьмутараканска. При этом были чётко зафиксированы в хронологическом порядке и координаты ячеек, которые были заклеены, и буквы, которыми они были заклеены. Наказание (или поощрение) за незаконную агитацию по Тьмутараканским законам зависит от того, насколько был нарушен баланс в пользу той или иной коалиции. Иными словами, насколько больше одних букв, чем других оказалось в некоторой прямоугольной области рекламного щита.
Ваша задача – написать программу, которая по имеющейся видеозаписи будет вычислять количество букв А и В в заданной прямоугольной области на данный момент времени.

Формат входных данных
В первой строке входного файла записано целое число N – суммарное количество актов заклеивания и запросов (1
· N
· 106). В остальных N строках записано:
- или буква A (или B) и два целых числа x, y (1
· x, y
· 1024);
- или буква R и четыре целых числа x1, y1, x2, y2 (1
· x1
· x2
· 1024, 1
· y1
· y2
· 1024).
Строка первого вида (AB-строка) означает, что в данный момент зафиксировано заклеивание ячейки с координатами x, y буквой A (B). Строка второго вида (R-строка) означает, что программа должна подсчитать количество букв А и букв В в прямоугольной области с координатами противоположных углов x1, y1 и x2, y2 в данный момент времени.

Формат выходных данных
Для каждой R-строки во входном файле запишите в выходной файл количество букв А и количество букв В в заданной области.

Примеры входа и выхода
election.in
election.out

7
R 1 1 3 3
A 2 3
A 1 3
R 1 1 3 3
B 2 2
B 3 3
R 2 2 3 3
5 4
6 3
1 3



15

Приложенные файлы

  • doc 6503246
    Размер файла: 61 kB Загрузок: 1

Добавить комментарий