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

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

HotLog


 
[Вернуться к задаче]   1
  1  Матус Даниил Дмитриевич, 06 сентября 2020 г. 15:49:30
     ху сдал с приорити куе но не с перового трая ибо тл из зи чтения долгого прописал по стандарту ios_base::sync_with_stdio(false); cin.tie(NULL); и все ас
  2  Данияр Бекишев, 29 апреля 2020 г. 2:38:15
     BinarySearch вам в помощь)
  3  Дмитрий Козырев, 02 апреля 2019 г. 15:52:59
     Чтобы решить проблему с непрерывностью времени, а не дискретностью, можно все координаты умножить на 2, и посетить x-1, x, x+1. Тогда получается, что будут посещены моменты половинного времени, кратные 0.5
  4  Сапожников Денис Сергеевич, 03 сентября 2018 г. 18:07:46
     Пихать задачу по мл это такое себе удовольствие :(
     Если при N=100 тыс памяти 16 Мб, то это по 160 байт на одну карту. По ощущениям это очень много.
  5  Цыкин Святослав Витальевич, 02 августа 2017 г. 8:35:50
     сдал за 0.78 c STL
  6  Фертиков Роман, 20 ноября 2016 г. 12:27:03
     деревом отрезков слишком много времени на 4м тесте
  7  Ислом Искандаров, 24 августа 2015 г. 15:24:50
     Можно Деревом отрезков находить ответы для подзадач :)
  8  Иван Михнович, 03 мая 2015 г. 21:23:46
     Мне почему-то весьма понравилась эта задачка. Вообще она простая, но я с ней непозволительно долго кувыркался через голову :o)

Весь челлендж в том, чтобы для любого момента времени уметь быстро (хотя бы за log(n)) определять самую дешевую из актуальных карт. Очевидно, это ответ на подзадачу. Она (подзадача) очень просто решается за линию, а вот за логарифм... Немного подумав, впрочем, я понял что благодаря некоторым особенностям задачи для её решения можно применить приоритетную очередь. И не своими руками же её писать? Здесь я применил монструозную конструкцию:
std::priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>

И ничего, зашло :o)
Правда я не уверен что не существует более простого решения. И вряд ли автор задачи подразумевал использование STL.
  9  Максим Мелеховец, 21 июня 2014 г. 22:34:47
     9 14 10 и 15 20 14 не пересекаются, т.к. в момент с 14 по 15 секунду не будет Интернета.
  10  Спас Ілля, 09 июня 2014 г. 23:21:16
     А почему в тестовом примере не подходит ответ 47? Т.е. при использовании следующих сетевых карт:
9 14 10; 15 20 14; 18 24 14; 24 30 9.
 1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

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