Guys i am stuck in this problem-http://www.spoj.com/problems/RATING/.Any help will be appreciated .
№ | Пользователь | Рейтинг |
---|---|---|
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 |
2 | maomao90 | 163 |
4 | atcoder_official | 161 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | nor | 153 |
9 | Dominater069 | 153 |
Guys i am stuck in this problem-http://www.spoj.com/problems/RATING/.Any help will be appreciated .
Название |
---|
this problem requires the knowledge of data structure such as segment tree or fenwick tree.
sort according to the values of any rating (open or school ratings — i have considered open ratings in my explanation)
(think yourself why we need sorting ?)
query for no of hashes less than equal to corresponding high school ratings — name it res
for every coder sharing same value of open and high school ratings, assign them res (justify yourself why ?) and update the tree with his high school rating.
UPD : I found one good explanation from codechef discussion page.
here
here