Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Космическое сновидение

(Время: 3 сек. Память: 64 Мб Сложность: 67%)

Аня любит читать книги, недавно ей посоветовали книгу известного физика-теоретика о чёрных дырах. Прочитав пару глав, она легла спать, и ей приснился странный сон.

Во сне девочка увидела систему из планет и чёрных дыр, местоположение которых можно представить на оси Ox. Как известно, чёрные дыры могут поглощать другие космические тела, в данной системе это свойство также сохраняется, причём каждая чёрная дыра действует на расстояние wi и имеет мощность pi. Пусть d − расстояние между планетой и чёрной дырой, равное модулю разности их координат. Чёрная дыра будет оказывать воздействие на эту планету только в том случае, если d ≤ wi, при этом она будет поглощать планету с силой pi - d. Может оказаться так, что на планету воздействует несколько чёрных дыр, в таком случае считается, что планета будет поглощена той чёрной дырой, которая действует на неё с наибольшей силой, при наличии нескольких таких чёрных дыр, планета может быть поглощена любой из них, в таком случае считается, что заранее предсказать исход невозможно.

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

Подумав некоторое время, девочка поняла, что эта задача ей не под силу, поэтому попросила вас помочь ей найти решение.

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

Первая строка входного файла INPUT.TXT содержит число n (1 ≤ n ≤ 2·105) − количество небесных тел. Каждая из следующих n строк содержит информацию об очередном небесном теле:

  • планета задаётся в формате «1 xi», где xi − координата i-й планеты (-109 ≤ xi ≤ 109).
  • чёрная дыра описывается в формате «2 xj pj wj», где параметрам соответствуют − координата j-й черной дыры, мощность и дальность её воздействия (-109 ≤ xj ≤ 109; 1 ≤ wj < pj ≤ 2·109).

Все числа во входных данных являются целыми. Гарантируется, что существует хотя бы одна планета и в каждой точке может находиться не более чем один космический объект.

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

В первой строке выходного файла OUTPUT.TXT выведите одно число k − количество планет во входных данных.

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

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

Примеры

INPUT.TXTOUTPUT.TXTПояснение
15
1 4
2 2 6 3
2 -1 10 5
1 5
1 -4
3
2 1 2
24
1 3
2 6 4 3
2 1 3 2
1 -2
2
1 -1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 A. Переполох у турникетов
 B. Поездка в кино
 C. Баобаб
 D. Очистка террасы
 E. Битва школ
 F. Этажи
 G. Космическое сновидение
 H. Неумолкающий Янпул
 I. ЦПСП
 J. Стреляй!
 K. Отряд Стёпы
 L. Swap optimization

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru