Hello,
could anyone provide good source for understand and solving GSS1 of spoj.
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
11:57:07
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
11:57:07
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 30.11.2024 05:37:54 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
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.