Подскажите пожалуйста, как решать задачу С.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | cry | 158 |
4 | awoo | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | maroonrk | 152 |
Название |
---|
Это не есть доказательство верности алгоритма.
http://pastie.org/1828216
По идее там для каждой переменной надо создать 2 вершины, а каждое неравенство порождает 2 дуги. Т.к. для соединённых дугой остаточной сети вершин есть неравенство на потенциалы и стоимость дуги, то правильно расставив дуги можно получить те неравенства, которые требуются, точнее попробуйте продумать сами. Но вообще это довольно известное сведение, можно и загуглить.
Я написал scanline + set. Но получил TL 9. Всего событий 2*N. Проход по сету для объединения отрезков - O(N). Добавление отрезка и удаление из сета - O(logN). В среднем должно выходить O(N^2 + 2*N*logN). В сортировке событий и сете оперировал только индексами.
А как решать за O (N*logN) ?