Че-то никак мысли не приходят, вроде простая задача должна быть, на форуме написано, что решается множеством способов. Может кто-нибудь подробно написать решение?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 4 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 14.11.2024 20:05:33 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
И она используется при изучении следующих тем:
- sqrt-декомпозиция
- дерево Фенвика
- дерево отрезков
- декартово дерево
Отсортируем все точки по координате X, при равенстве X - по Y. Очевидно что в получившейся последовательности для некоторой позиции i, все точки имеющие позиции большие чем i находятся либо правее либо выше (с учетом того, что двух одинаковых точек быть не может). Причем все точки которые имеют позиции меньшие чем i находятся не правее. Т.е задача свелась к тому, что нужно для каждой точки определять сколько точек из тех, что находятся в отсортированной последовательности левее данной, находятся не выше.
Для этого сделаем следующее:
Заведем нитервальное дерево для суммы, изначально пустое. Будем идти по отсортированным точкам. Level текущей точки будет сумма в дереве от 0 до Y текущей точки. После того, как мы узнали Level текущей точки, нужно увеличить элемент с номером Y текущей точки на единицу.
Вот так будет работаеть тест из примера:
изначально есть:(1 1), (5 1), (7 1), (3 3), (5 5)
после сортирования:
(1 1), (3 3), (5 1), (5 5), (7 1)
Собираем решение:
итерация 1.
дерево сумм[0.. maxY]: 0 0 0 0 0 0
ответ [0.. n - 1]: 0 0 0 0 0
позиция 0:
Берем в дереве сумму с 0 по 1, она равна 0. в ответ добавляем одну точку 0 уровня. В дереве увеличиваем элемент [1] на единицу.
итерация 2.
дерево сумм[0.. maxY]: 0 1 0 0 0 0
ответ [0.. n - 1]: 1 0 0 0 0
позиция 1:
Берем в дереве сумму с 0 по 3, она равна 1. в ответ добавляем одну точку 1 уровня. В дереве увеличиваем элемент [3] на единицу.
итерация 3.
дерево сумм[0.. maxY]: 0 1 0 1 0 0
ответ [0.. n - 1]: 1 1 0 0 0
позиция 2:
Берем в дереве сумму с 0 по 1, она равна 1. в ответ добавляем одну точку 1 уровня. В дереве увеличиваем элемент [1] на единицу.
итерация 4.
дерево сумм[0.. maxY]: 0 2 0 1 0 0
ответ [0.. n - 1]: 1 2 0 0 0
позиция 3:
Берем в дереве сумму с 0 по 5, она равна 3. в ответ добавляем одну точку 3 уровня. В дереве увеличиваем элемент [5] на единицу.
итерация 5.
дерево сумм[0.. maxY]: 0 2 0 1 0 1
ответ [0.. n - 1]: 1 2 0 1 0
позиция 4:
Берем в дереве сумму с 0 по 1, она равна 2. в ответ добавляем одну точку 2 уровня. В дереве увеличиваем элемент [1] на единицу.
дерево сумм[0.. maxY]: 0 3 0 1 0 1
конечный ответ [0.. n - 1]: 1 2 1 1 0
Вот так мы получили ответ. Для того, чтобы посмотреть как строить дерево для сумм, можно почитать на вики статю про RSQ, или дерево Фенвика. Запросы взять сумму и обновить элемент дерева будут работать за log(maxY), всего такиз запросов нужно будет выполнить N. Итого вычислительная сложность порядка Nlog(N)
Не туда :(
сложность o(n*sqrt(n)*log(maxy))
Может можно как-нибуть по-другому?
Напишите пожалуйста!
всё гораздо проще, если отвечать на входные данные сразу. ( онлайн )
так как входные данные подаются по отсортированному Y, то можно его вообще отбросить, так как роли он никакой не играет.
в итоге задача свелась к нахождению количества чисел находящихся не правее данного.
и теперь можно делать sqrt-декомпозицию только для [0;32000], а не [0;32000]*[0;32000]. =)
Вспомнил тот прикол, что когда я стал соадмином одного АСМ-сайта, и начал иногда из интереса читать коды знакомых по некоторым задачам, то сразу нашел штук 10 задач, где кривые тесты и проходит явный бред:)
Хотя иногда полезно бывает "не умничать" и придумать простенькое решение.
А эту задачу с тимуса я тоже sqrt-декомпозицией делал.