FreeCam, Партия из двух шариков делается за 4 минуты. Нужен один шарик. Будет 4 минуты, ты это никак не ускоришь.
Другой пример: если свинья беременна 4 месяца и приносит 5 поросят, то один хрен нужно ждать 4 месяца, чтобы получить одного поросёнка.
Proshka17,
Как я уже написал, надо чётко понимать, какое условие «один поддон встанет на другой». Если меньше по обоим измерениям — то [begin, LOWER_bound). Мы ищем поддоны, которые встанут на наш.
Выяснил, что можно обойтись без трюкачества с условием сравнения — просто…
1. Если it1 = begin, BREAK
2. --it1
3. Если этот поддон НЕ встанет на наш, BREAK
4. it1 := erase(it1).
5. Повторить.
Каждая итерация цикла — log n, при этом итераций НА ВСЮ ПРОГРАММУ не больше n.
Цикл на условие «меньше по обоим измерениям», если условие другое — то и цикл другой.
Proshka17, Я думал, это какая-то разглючка, связанная с изменением дерева.
Ничего удалять на надо! Это значит у всех, у кого first < p.first, будет second > p.second.
И второе я нашёл — с таким lower_bound надо сверить на всякий случай first. Ведь не исключено, что it2 > it1, но сравнивать такие итераторы невозможно. В таком случае тоже ничего не делаем.