I have tried to use the Sparse Table Algorithm in order to compute the RMQ in this problem. However, this ends up timing out. I thought it was O(nlogn)?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
I have tried to use the Sparse Table Algorithm in order to compute the RMQ in this problem. However, this ends up timing out. I thought it was O(nlogn)?
Name |
---|
Auto comment: topic has been updated by miniluigi (previous revision, new revision, compare).
Try mend your binary search, like here and your RMQ dubious
Thanks! That helped me overcome the TLE
Shouldn't it be log2(j — i + 1)? It would be better if you precalculate logarithms.
Thanks! I fixed that.