Кто-нибудь можете помочь с этой задачей? Есть какие-нибудь идеи для её решения? (У самого есть одна идея , но её реализация на С++ составит примерно 200-250 строк..может есть идеи по-лучше)
Спасибо.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3757 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 171 |
2 | awoo | 165 |
3 | adamant | 164 |
4 | TheScrasse | 159 |
5 | maroonrk | 154 |
6 | nor | 153 |
7 | -is-this-fft- | 152 |
8 | Petr | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
Кто-нибудь можете помочь с этой задачей? Есть какие-нибудь идеи для её решения? (У самого есть одна идея , но её реализация на С++ составит примерно 200-250 строк..может есть идеи по-лучше)
Спасибо.
Название |
---|
По сути требуется структура, которая умеет быстрее квадрата делать присваивание на отрезке и за разумное время выгружать все данные в массив. Двумерное дерево отрезков такими способностями, как я знаю, не обладает.
Зато можно применить массив размера A из одномерных деревьев отрезков. Запрос будет обрабатываться за , что вполне приемлимо. Если сделать сжатие координат, то точно зайдёт (возможно, если попихать, то с ним зайдёт и квадрат)
Сможешь объяснить как именно сжатие координат надо сделать?
Смогу, но не могу открыть условие — регистрацию просят, а она не помогает.
Сжатие координат — это какой-то такой код:
Теперь точки у нас имеют координаты от 0 до n - 1, а относительный порядок сохранился. Чтобы сделать запрос к [L, R] в исходных координатах, надо сделать запрос от
lower_bound(xs.begin(), xs.end(), L) - xs.begin()
доupper_bound(xs.begin(), xs.end(), R) - xs.begin() - 1
(включительно)На USACO Memory limit.
Попытался сдать ту же задачу на тимусе. 1147.Цветная Бумага.
Wrong Answer 7.
Не могли бы сказать в чем ошибка?