| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Can someone provide some hint for solving this prbolem of spoj www.spoj.com/problems/LIS2/. The approach I am trying is very similar to the LIS dp solution(O(Nlogn)). But my solution doesnot give correct answer for all cases I am testing upon.
Here is the rough idea of what I am doing : http://ideone.com/kyIJMf
So I'm not the only one... I've tried it too, but also haven't got AC yet. Looks like the standard LIS problem modified by only int pairs due to the condition "A pair of integers (x1, y1) is less than (x2, y2) iff x1 < x2 and y1 < y2." So if it couldn't be handled like the standard LIS, I'm really out of ideas.
I saw this http://stackoverflow.com/questions/17378305/approach-to-lis2-on-spoj . However, unable to grasp clearly the approach written,
Guess I should learn something about segment trees :D