| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 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 |
I was trying to learn Mo's Algorithm from here and this was one of the suggested problems. But, I'm getting TLE verdict with Java, while my code is very similar to the one that the tutorial's author has written, in C++.
Can someone please tell me what am I doing wrong(slow)? Thanks.
UPDATE : Sorry, forgot to post a link for my code
Auto comment: topic has been updated by rahulkhairwar (previous revision, new revision, compare).
I did not trace your code, but SPOJ is very strict judge. Some problems are only solvable in C++.
So sometimes no matter how much you optimise your Java's code, it won't pass.
but there are 3 people who have solved this problem in Java
Perhaps they use a faster algorithm.
slow input !?
no, I'm using fast input
I believe your solution should pass as the time complexity is acceptable. But, as many people have already pointed out, SPOJ is pretty strict when it comes to TLEs.
However, there is a faster solution than yours. Try to come up with a solution using BIT.
Same here for my java code too. Tried all kinds of optimizations and gave up. I tried searching those 3 ppl (whose java passed) on codeforces but no luck A couple other similar tight tle problems were also solved by some of the 3.