Hello,
could anyone provide good source for understand and solving GSS1 of spoj.
Hello,
could anyone provide good source for understand and solving GSS1 of spoj.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 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 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
You better knew how to use Interval Tree before to solve this. At each node K of the IT we will need 4 values: 1. sum: sum of all elements in the interval managed by node K 2. left: the maximum continuous sum starts from the left (prefix sum) of the interval managed by node K 3. right: the maximum continuous sum starts from the right (suffix sum) of the interval managed by node K 4. res: maximum sum of the interval managed by node K (that's it, the answer we need)
When we combine two intervals: - New.sum = L.sum + R.sum - New.left = max(L.left , L.sum + R.left) - New.right = max(R.right , L.right + R.sum) - New.res = max(L.res , R.res , L.right + R.left)
Hope it will help you.
In this page you can find awesome solution and explanation for SPOJ's GSS1 and here discussion for it and also many other problems solved using segment tree and it's variations.