Problem says that we have to get rank of the favourite team after updating rank of team t at each query. Can anybody suggest me how to solve this online query problem?
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Dec/22/2024 23:43:52 (j2).
Desktop version, switch to mobile version.
Supported by
Your rank is number of teams with more problems than you + number of teams with same problems as you but less penalty.
We can calculate the number of teams with more problems by using binary indexed tree built over problems where they contain the number of teams that solved them, then the number of teams with larger problems is query(maximum_problems) — query(team #1 problems). After each query make sure you update your BIT.
For the second part use K balanced binary trees which contains the penalties of each team that currently have solved exactly p problems. Then you need something to answer kth order statistics queries which you can implement quickly using this link, and again after each event update your balanced binary trees. ( Memory usage will be O(N) because we store teams that solved exactly P problems).
Thanks for your reply. It's the second time I am coming across Policy-based Data structures. Java does not have such inbuilt library for Ordered Set :( I have a doubt regarding Ordered Set. Is ordered set a type of treap? If it's a variance of Treap, what extra factors are added in Treap to make it work like Ordered Set. As I want to implement it in Java, without knowing the functioning I can't code it.