1 Тема от MSDN

  • MSDN
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-09
  • Сообщений: 40

Тема: Singapore 2007

Здравствуйте!

Есть вопросы по нескольким задачам

SKYLINE

http://acmicpc-live-archive.uva.es/nuev … php?p=4108

Собственно похоже что задача на дерево отрезков... но вот как решать так и не придумал.

TUSK

http://acmicpc-live-archive.uva.es/nuev … php?p=4107

Вроде написал выметание... но потом понял что решение не канает вкорне.

2 Ответ от Oleg Отредактировано Oleg (2010-09-30 13:52:50)

  • Oleg
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-09-22
  • Сообщений: 86

Re: Singapore 2007

Решил SKYLINE деревом отрезков. Кроме height еще сохраняй minValue и maxValue.
Скопировал в http://ideone.com/Njt4I если не разберешься.

3 Ответ от MSDN Отредактировано MSDN (2010-09-30 14:26:47)

  • MSDN
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-09
  • Сообщений: 40

Re: Singapore 2007

Oleg пишет:

Решил SKYLINE деревом отрезков. Кроме height еще сохраняй minValue и maxValue.
Скопировал в http://ideone.com/Njt4I если не разберешься.

Спасибо огромное.

Вообще была такая идея, ну или подобная. Но я ее откинул потому что тест можно придумать - типа "зубья", то есть сначала идет очень высокий прямоугольник, потом очень низкий, потом снова высокий и т.д. А потом можно добавить прямоугольник (по высоте выше низких и ниже высоких), который пересекает все эти "зубья" и получается что обновление произойдет за линейное время.

4 Ответ от mincer

  • mincer
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-19
  • Сообщений: 12

Re: Singapore 2007

Вообще нехорошая задача этот SkyLine. Там как раз ограничение на ответ в 2*(10^6) и дает то, что такого теста не будет. Получается, что количество просмотров всех узлов дерева как раз и не превысит два лимона априорно. Вот если бы ограничения этого не было, то тест "с зубьями" корректен, и будет работать за квадрат sad